투 포인터 (two pointers)

투포인터

투포인터 알고리즘에 대해 알아보자.

투포인터는 선형시간 O(n)으로 알고리즘을 풀 수 있게 만들어주는 마법의 알고리즘이다.

투포인터는 간단한 편이라 한번쯤 익혀두면 구현하는 것은 어렵지 않을 것이다.

 

하지만, 시간이 지나면 기억은 흐릿해지기 때문에 다시 찾아 볼 수 있도록 정리해두려고 한다^^,,

투포인터는 연속적인 값들을 이용해 푸는 문제에 적합하다.

 

문제

2003번: 수들의 합 2

위 백준의 2003번 문제를 통해 투포인터 알고리즘을 알아보도록 하겠다.

 

우선 나는 문제를 처음 읽었을 때 익숙하게 2중 for문을 사용하는 방식이 떠올랐다. 하지만 2중 for문을 사용할 경우 O(n2)의 시간복잡도를 가지게 된다.

이렇게 연속적인 값들을 이용할 때 투포인터 알고리즘을 사용하게 되면 O(n2) → O(n)으로 풀 수 있다.

 

풀이

풀이 코드

class Main {
    static int solution(int n, int m, int[] arr) {
        int cnt = 0; // 경우의 수
        int sum = 0;

        // 투 포인터
        int lt = 0;
        for (int rt = 0; rt < n; rt++) {
            sum += arr[rt];

            if (sum == m)
                cnt++;

            while (sum >= m) {
                sum -= arr[lt++];

                if (sum == m) 
                    cnt++;
            }
        }

        return cnt;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 수열의 개수
        int m = sc.nextInt(); // 합

        int[] arr = new int[n];

        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();

        System.out.println(solution(n, m, arr));
    }
}

 

풀이 설명

• 배열의 인덱스를 가리키는 두 개의 포인터를 만든다. (lt는 시작지점, rt는 끝지점을 가리킨다.)
• rt가 0부터 n(배열의 크기)까지 돌면서 sum에 값을 더해준다.
  
  • sum == m : 합계가 찾고자 하는 값이 되면 cnt(경우의 수 개수)를 하나 늘려준다.
  • sum >= m : 합계가 찾고자 하는 값보다 크거나 같다면, lt에 해당하는 값을 차례로 sum에서 빼준다. (sum이 m보다 작아질 때 까지)
    • 이때도 마찬가지로 sum==m이 같아지는 경우를 체크하며, 같을 경우 cnt를 하나 늘려준다.
• 반복을 모두 돌면 수열의 합이 m이 되는 경우의 수(cnt)를 return 한다.

 

조금 더 이해하기 쉽도록 그림으로 설명하겠다.

배열 {1, 2, 3, 2, 5}에서 합이 5가 되는 경우의 수를 구한다고 생각해보자.

sum의 값이 5보다 작음. rt+1

sum의 값이 5보다 작음. rt+1

sum의 값이 5보다 크다. lt+1

sum의 값이 5와 같다. cnt+1, lt+1

sum의 값이 5보다 작음. rt+1

sum의 값이 5와 같다. cnt+1, lt+1

sum의 값이 5보다 작음. rt+1

sum의 값이 5보다 크다. lt+1

sum의 값이 5와 같다. cnt+1, 반복문 종료

 

이렇게 투포인터 알고리즘은 두개의 포인터를 이동시키며 연속 된 값에 접근하기 용이한 알고리즘으로, 

코딩 테스트에 정말 자주 등장하기 때문에 정리해보았다. 😊