[자바] 투 포인터(Two Pointers) 알고리즘

Two Pointers

 

배열에서 두 개의 포인터를 갖고 원하는 결과를 얻는 알고리즘을 일컫는다.

 

각 포인터의 배치방법은 두 가지가 있다.

• 두 포인터 모두 배열의 첫 번째 원소에 배치
• 각각 첫 원소와 마지막 원소에 배치

 

 

투 포인터를 사용하지 않고 단순 이중 for문으로 문제를 해결한다면, 시간복잡도에서 효율성이 다소 떨어질 수 있다.

예를 들어 위 배열에서 합이 7을 이루는 부분배열을 찾고자 한다면,

i를 index 0에 두고 j를 index 1부터 배열의 끝까지 가면서 찾으면된다.

j가 끝까지 도달했다면 i를 index 1로 한칸옮기고 j는 다시 index 2부터 배열의 끝까지 간다.

코드로 간단히 나타내면 이렇다.

public static int[] forExample(int[] arr, int target) {
        int[] result = {-1, -1};

        totalbreak:
        for (int i = 0; i < arr.length; i++) {
            int sum = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (sum == target) {
                    result[0] = i;
                    result[1] = j - 1;
                    break totalbreak;
                }
                sum += arr[j];
            }
        }
        return result;
    }

이 방법은 구현하기 간편한 장점이 있지만, 시간복잡도가 O(n^2)이다.

시간의 효율성을 중요하게 평가하는 코딩테스트에서 큰 단점으로 다가올 수 있다.

 

 

 

---

위 예시를 투 포인터로 푼다면 시간복잡도를 O(n)까지 낮출 수 있다.

아래 예시를 보자.

마찬가지로 합이 7을 이루는 부분배열을 찾고자 한다.

우리는 먼저 i와 j를 함께 index 0에 둘 것이다.

그리고 i만 한칸씩 이동하면서 j와 합해간다.

1+2 -> 1+2+5 -> 1+2+5+3 ... 이런 방식으로 말이다.

그러다 중간에 7보다 값이 크다면 j를 한칸 당겨오고 이전에 더했던 j값을 빼준다. (1+2 -> 1+2+5 -> 2+5)

이동했는데도 7보다 크다면? j를 한칸 더 당겨온다.

이렇게 i와 j가 배열의 끝까지 도달하면서 부분배열을 찾을 수 있을것이다.

 

두 포인터를 left와 right로 선언하고 구현하면 다음과 같다.

public static int[] twoPointers(int[] arr, int target) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int[] result = {-1, -1};

        while(true) {
           if (sum > target) { // 두 포인터의 합이 target보다 크면 left를 하나 줄인다.
               sum -= arr[left++];
           } else if (right == arr.length) { // right 포인터가 끝까지 도달한다면 반복문을 탈출한다.
               break;
           } else {
               sum += arr[right++]; // 두 포인터의 합이 target보다 작으면 right를 하나씩 늘려가며 sum에 더한다.
           }

           if (sum == target) {
               result[0] = left;
               result[1] = right - 1;
               break;
           }
        }
        return result;
    }
    
        public static void main(String[] args) {
        int[] arr = {1, 2, 5, 3, 7, 2, 4, 3, 2};

        System.out.println(Arrays.toString(twoPointers(arr, 14))); // 출력: [4,5]
    }

 

여기까지 투포인터를 구현해보았다.

마지막으로 간단한 예제 하나를 풀어보곘다.

예제

문자열 양 끝이 같다면 해당 문자를 삭제하는데, 삭제되는 문자와 같은 문자가 연속해서 등장한다면 함께 삭제한다.

ex) 입력: aabbccdbaa  /  출력:  ccd

 

투포인터 문제에서 꼭 두 포인터를 동일선상 맨 앞에 두고 출발할 필요는 없다.

이번 예제는 문자열 맨 앞과 맨 뒤를 비교하는 문제이며,

각 포인터를 문자열 맨 앞, 맨 뒤 부터 시작해 가운데로 이동하며 비교해보겠다.

 

public static String solution(String s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right && s.charAt(left) == s.charAt(right)) {
            char c = s.charAt(left);
            while (left <= right && s.charAt(left) == c) {
                left++;   // 왼쪽에서 동일한 문자열이 연속된다면 줄여나간다.
            }

            while (left <= right && s.charAt(right) == c) { 
                right--;  // 오른쪽에서 동일한 문자열이 연속된다면 줄여나간다.
            }
        }
        return s.substring(left, right + 1);
    }

       public static void main(String[] args) {
         System.out.println(solution("aabbccdbaa"));  // ccd
    }

 

투포인터 알고리즘 구현 및 예제풀이를 마치겠다.