[알고리즘] 투 포인터 사용하기

 

투 포인터 알고리즘?

정렬되어 있는 배열에서 크기를 비교하기 위해서 사용되는 알고리즘이다.

 

이게 왜 좋냐면, 투 포인터 알고리즘 자체가 O(logN)을 보장하기 때문이다. 즉, 시간 초과를 막기 위한 효율적인 수단 중 하나이다.

 

일반적인 자바 정렬의 경우(Arrays.sort())에는 O(nlogN)의 시간 복잡도를 가지고 있으므로, 정렬과 투 포인터를 사용할 만한 상황인 지 점검할 필요가 있다.

 

1. 정렬이 되어 있는가?
투 포인터는 정렬된 경우에 가장 효율적이다. 만약 되어있지 않다면, 정렬 알고리즘을 적용시킨 시간 복잡도를 고려해야 한다.
2. 문제에서 크기를 비교하는 것을 요하는가?
위 조건을 만족시킨다고 했을 때, 크기를 서로 비교하는 문제를 해결하는데 효율적이다.

 

 

예시 문제 적용 방법

 

백준 1253번 문제에서 투 포인터를 사용할 수 있다.

문제에 대해 궁금하다면, 아래 링크를 참고하여 읽어보길 바란다.

 

1253번: 좋다

 

내가 푼 방법은 아래와 같다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
    	// Scanner와의 차이로는 버퍼 사이즈 차이(Scanner : 1KB, Buffer..: 8KB)
        // 또한 BufferedReader는 String 내놓는다.
        // InputStreamReader를 통해 바이트 기반 스트림을 문자 기반 스트림으로 변환
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());

        StringTokenizer st = new StringTokenizer(bf.readLine());
        long[] A = new long[N];

        for(int i=0; i<N; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(A);
        int count = 0;
        for(int K=0; K<N; K++) {
            int i=0;
            int j=N-1;
            while(i < j) {
                if(A[i] + A[j] < A[K]) {
                    i++;
                } else if (A[i] + A[j] > A[K]) {
                    j--;
                } else if (A[i] + A[j] == A[K]) {
                    if (i != K && j != K) {
                        count++;
                        break;
                    } else if (i == K) {
                        i++;
                    } else if (j == K) {
                        j--;
                    }
                }
            }
        }
        System.out.println(count);
    }
}

 

투 포인터 알고리즘의 핵심은 i와 j의 유동적인 인덱스 움직임이다.

즉, i와 j는 각각 정렬된 배열의 끝단에 위치한다.

그리고, 주어진 조건에 따라서 i와 j를 한 칸씩 앞 뒤로 이동시킨다. 위 문제 처럼 조건이 조금 더 있다면 추가해 주면된다.(이 부분이 어려운 문제와 쉬운 문제를 나누는 기준인 듯 하다.)

 

이 문제는 좋은 수 K자체만으로는 조건을 만족시킬 수 없게 해야 한다. 무조건 두 수의 합이어야 가능하다는 것이다. 

 

 

 

Reference

- Do it! 알고리즘 코딩 테스트 자바 편