[개념 정리] 투 포인터

최근 알고리즘을 풀면서 시간 초과와 예외처리로 인해 상당히 애를 먹었던 문제가 있다. 해당 문제의 다른 풀이를 찾아보니 투 포인터 알고리즘을 통해 간단하게 구현할 수 있다는 점을 알았고 이에 대해 정리해보고자 한다. 투 포인터 알고리즘은 하나의 배열에서 두 개의 인덱스 포인터를 조작하는 알고리즘을 의미한다. 문제를 예시로 들어서 설명하면 다음과 같다.

백준 - 2467. 용액

이 문제에서 0과 가장 가까운 거리의 합을 가지는 두 원소를 구하는 방법은 먼저 O(N^2)의 시간복잡도를 가지는 방법이 존재한다. 하지만 문제처럼 N의 크기가 O(N^2)으로 해결할 수 없는 경우에 투 포인터 알고리즘을 사용하면 O(N)에 해당 값을 구할 수 있다. (이 문제는 정렬이 필요하기 때문에 전체 문제의 시간복잡도는 O(NlogN)이다. 하지만 투포인터 알고리즘의 시간복잡도는 O(N)이다.)

풀이 방법은 먼저 용액의 특성값을 오름차순으로 정렬한다. 그리고 Left : 0 / Right : N - 1로 초기값을 설정한 후에 특성값의 합을 구한다. 만약 left의 특성값과 right의 특성값의 합이 0보다 작으면 0과 가까워지기 위해서는 left를 더 큰값으로 바꿔줘야 한다. 반대 경우에는 right를 더 작은 값으로 바꿔줘야 한다. 이 과정에서 0과의 거리의 최소값을 갱신하면서 진행하면 O(N)에 최소값을 구할 수 있다.

Java로 작성한 코드는 다음과 같다.

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

public class Solution2467 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int[] map = new int[N];
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            map[i] = Integer.parseInt(input[i]);
        }
        Arrays.sort(map);
        int left = 0, right = N - 1;
        int min = Integer.MAX_VALUE;
        int[] answer = new int[2];

        while(left < right) {
            int sum = map[right] + map[left];
            if (min > Math.abs(sum)) {
                min = Math.abs(sum);
                answer[0] = map[left];
                answer[1] = map[right];
            }

            if (sum > 0)
                right--;
            else
                left++;
        }

        System.out.println(answer[0] + " " + answer[1]);
    }
}

 

TMI

해당 문제에 대해 투 포인터 알고리즘을 사용하지 않은 풀이는 다음과 같다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Solution2470 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        ArrayList<Integer> positive = new ArrayList<>();
        ArrayList<Integer> negative = new ArrayList<>();
        int N = Integer.parseInt(br.readLine());

        String[] input = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            int cur = Integer.parseInt(input[i]);
            if (cur > 0)
                positive.add(cur);
            else
                negative.add(cur);
        }
        positive.sort(Integer::compareTo);
        negative.sort(Collections.reverseOrder());
        int positiveMin = (positive.size() >= 2) ? Math.abs(positive.get(0) + positive.get(1)) : Integer.MAX_VALUE;
        int negativeMin = (negative.size() >= 2) ? Math.abs(negative.get(0) + negative.get(1)) : Integer.MAX_VALUE;

        int[] result = new int[2];
        int min = Math.min(positiveMin, negativeMin);

        int positiveIdx = 0;
        int negativeIdx = 0;
        int positiveDidx = 0;
        int negativeDidx = 1;
        int curPos = -1000000001, curNeg = 1000000001;
        while (positiveIdx < positive.size() && negativeIdx < negative.size()) {
            curPos = positive.get(positiveIdx);
            curNeg = negative.get(negativeIdx);
            int curMin = Integer.MAX_VALUE;
            int[] temp = new int[2];
            while(positiveIdx < positive.size() && negativeIdx < negative.size()) {
                curPos = positive.get(positiveIdx);
                curNeg = negative.get(negativeIdx);
                if (curMin < Math.abs(curPos + curNeg)) {
                    positiveIdx -= positiveDidx;
                    negativeIdx -= negativeDidx;
                    positiveDidx = (positiveDidx + 1) % 2;
                    negativeDidx = (negativeDidx + 1) % 2;
                    break;
                }
                curMin = Math.abs(curPos + curNeg);
                temp[0] = curNeg;
                temp[1] = curPos;
                positiveIdx += positiveDidx;
                negativeIdx += negativeDidx;
            }

            if (min > curMin) {
                min = curMin;
                result[0] = temp[0];
                result[1] = temp[1];
            }

            positiveIdx += positiveDidx;
            negativeIdx += negativeDidx;
        }


        positiveIdx = (positiveIdx == positive.size()) ? positiveIdx - 1 : positiveIdx;
        negativeIdx = (negativeIdx == negative.size()) ? negativeIdx - 1 : negativeIdx;
        while (!positive.isEmpty() && positiveIdx < positive.size()) {
            curPos = positive.get(positiveIdx++);
            if (min > Math.abs(curPos + curNeg)) {
                min = Math.abs(curPos + curNeg);
                result[0] = curNeg;
                result[1] = curPos;
            }
        }

        while (!negative.isEmpty() && negativeIdx < negative.size()) {
            curNeg = negative.get(negativeIdx++);
            if (min > Math.abs(curPos + curNeg)) {
                min = Math.abs(curPos + curNeg);
                result[0] = curNeg;
                result[1] = curPos;
            }
        }

        if (negativeMin <= positiveMin && negativeMin <= min) {
            System.out.println(negative.get(1) + " " + negative.get(0));
        } else if (positiveMin <= negativeMin && positiveMin <= min) {
                System.out.println(positive.get(0) + " " + positive.get(1));
        } else if (min <= positiveMin && min <= negativeMin) {
            System.out.println(result[0] + " " + result[1]);
        }
    }
}

이 방법은 양수 배열과 음수 배열로 나누어서 특성값의 합을 구하는 방식을 진행했다. 양수와 음수를 절대값의 오름차순으로 정렬한 후에 해당 인덱스에서 특성값의 절대값을 계산하면서 최소 거리를 갱신했다. 하지만 코드를 보면 알 수 있듯이 인덱스 조정 및 처리해야 할 예외 케이스가 너무 많아 복잡한 코드가 되었다. 다른 투 포인터 문제를 많이 풀어봐야겠다.