[Algorithm] 투 포인터 (Two Pointers)

1. 두 포인터(Two Pointers)

화살표 두 개에 의미를 부여해서 탐색 범위를 압축하는 방법

 

2. 투 포인터 두 가지 경우

(1) 1차원 배열 위에 2개의 포인터를 만드는 경우

• 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동
• 2개의 포인터가 양 끝에서 서로를 향해 이동

 

(2) 관찰을 통해서 문제에 등장하는 변수 2개의 값을 두 포인터로 표현하는 경우

 

2. TIP

<키워드>

• 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로"
• 곱의 최소, ..에 가까운 수

=> 이런 단어가 등장하면 Two Pointers 접근을 시도해 볼 가치가 있다.

 

3. (Example) BOJ 1806 - 부분합

이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램

(1) 가장 쉬운 방법 O(N^2)

• 왼쪽 시작 L 결정 => O(N)
• 오른쪽 끝을 R을 L부터 시작해서 이동 => O(N)
• => O(N^2)

 

• 정답을 위해 봐야 하는 것들

L이 이동할 때마다 L에서 시작해서 R을 이동시킨다.

• 볼 필요가 없는 부분

R이 이동하지 않기 때문에 검은색 부분은 다시 탐색할 필요가 없다.

=> sum이라는 변수로 합의 크기를 가지고 있고 L이 이동할 때마다 sum에서 index L인 값을 빼준다.

(2) 투 포인터 방법 O(N)

• 왼쪽 시작 L의 이동 횟수 N번
• 오른쪽 끝을 R을 이전의 R부터 시작해서 이동
• L, R이 각자 최대 N 번 이동하니깐, O(N)

(3) 구현

public class G4_1806 {
    static int N;
    static int S;
    static int[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String str = br.readLine();
        st = new StringTokenizer(str, " ");
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        A = new int[N+1];
        str = br.readLine();
        st = new StringTokenizer(str, " ");
        for (int i = 1; i <=N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        twoPointer();
    }

    static void twoPointer() {
        int R = 0;
        int sum = 0;
        int ans = N+1;
        for (int L = 1; L <=N; L++) {
            // L-1을 구간에서 제외하기
            sum -= A[L-1];

            // R을 옮길 수 있을 때까지 옮기기
            while (R+1 <=N && sum < S) {
                sum += A[++R];
            }

            // [L ... R] 의 합, 즉 sum이 조건을 만족하면 정답 갱신하기
            if (sum >= S) {
                ans = Math.min(ans, R-L+1);
            }
        }
        // ans 값을 보고 불가능 판단하기
        if (ans == N+1) ans = 0;
        System.out.println(ans);
    }
}

 

3. (Example) BOJ 2470 - 두 용액

서로 다른 두 용액을 더해서 합이 최대한 0에 가깝게 만들기

(1) 투 포인터 방법 O(N)

• 정렬하기 O(NlogN)
• 제일 작은 원소, 제일 큰 원소를 빠르게 알 수 있다.
• L : "남아 있는 것들 중" 제일 작은 원소
• R : "남아 있는 것들 중" 제일 큰 원소

1. 최소 + 최대 < 0 => 최소 입장에서는 최선책을 만난 상태. 짝을 찾았으니 삭제 (더 고려 X)
2. 최소 + 최대 > 0 => 최대 입장에서는 최선책을 만난 상태. 짝을 찾았으니 삭제 (더 고려 X)
3. L=R => 서로 다른 두 용액을 고를 수 없는 상태이므로 종료

최소 + 최대 < 0 => L++

최소 + 최대 > 0 => R++

최소 + 최대 > 0 => R++

최소 + 최대 < 0 => L++

L=R => 종료

(2) 시간, 공간 복잡도 계산하기

• 1) 배열 정렬 한 번 => O(NlogN)
• 2) 매 순간 L, R로 계산한 후에, 이동시키기 => O(N)
• 3) 총 시간 복잡도 : O(NlongN)

(3) 구현

public class G5_2470 {
    static int N;
    static int[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        A = new int[N+1];
        String str = br.readLine();
        st = new StringTokenizer(str, " ");
        for (int i = 1; i <=N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A, 1, N+1);
        twoPointer();
    }

    static void twoPointer() {
        int R = N;
        int L = 1;
        int minSum = Integer.MAX_VALUE;
        int[] ans = new int[2];
        while (L < R) {
            if (minSum > Math.abs(A[L] + A[R])) {
                minSum = Math.abs(A[L] + A[R]);
                ans[0] = A[L];
                ans[1] = A[R];
            }
            if (A[L] + A[R] > 0) {
                R--;
            } else {
                L++;
            }
        }
        System.out.println(ans[0] + " " + ans[1]);
    }
}