투 포인터 (Two Pointer)

투포인터

정렬된 리스트를 두 개의 포인터를 가지고 순차적으로 접근하면서, 두 포인터 구간의 값이 타겟 값과 같을 때까지 포인터를 조작하는 기법을 말합니다.

 

투포인터 알고리즘에 대해서는 검색만 해도 어떻게 로직이 돌아가는 지 쉽게 이해할 수 있을 거 같아서 저는 두 개의 포인터를 함께 활용할 때 얻을 수 있는 이점이 무엇인 지에 대해서 글을 써볼까 했습니다.

 

사실 이점은 1차원 배열을 한 번의 루프로 문제의 원하는 결과를 얻을 수 있다는 점입니다. 

 

코딩테스트 문제마다 다르겠지만, 저는 수들의 합2(2003) 문제를 가지고 비교를 해보았습니다.

결과는 사실 복잡도에서 큰 차이를 못느꼈습니다.

하지만, 새로운 알고리즘 유형이니 익힐 필요성은 있다고 생각했습니다.

 

그리고 투포인터 알고리즘은 구현 방식이 문제 별로 많이 다르다고 하니, 일단 기본적인 로직 구현 방법을 익히고 문제마다 투포인터가 어떤식으로 응용되는 지 익히면 좋을 거 같습니다.

 

수들의 합

2003번: 수들의 합 2

이중 반복문을 이용한 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = convertStrToInt(st.nextToken());
        int M = convertStrToInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] inputDataArr = new int[N];
        for (int i = 0; i < N; i++) inputDataArr[i] = convertStrToInt(st.nextToken());
        int count = 0;
        for (int i = 0; i < N; i++) {
            int sum = inputDataArr[i];
            if (sum == M) {
                count++;
                continue;
            }
            for (int j = i + 1; j < N ; j++) {
                if (sum + inputDataArr[j] > M) break;
                if (sum + inputDataArr[j] == M) {
                    count++;
                    break;
                }
                sum += inputDataArr[j];
            }
        }
        System.out.println(count);
    }

    private static int convertStrToInt(String input) {
        return Integer.parseInt(input);
    }
}

투 포인터를 이용한 풀이

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

public class Main {

    private static int convertStrToInt(String input) {
        return Integer.parseInt(input);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = convertStrToInt(st.nextToken());
        int M = convertStrToInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] inputDataArr = new int[N];
        for (int i = 0; i < N; i++) inputDataArr[i] = convertStrToInt(st.nextToken());

        int start = 0;
        int end = 0;
        int sum = 0;
        int cnt = 0;
        while (true) {
            // base case
            if (end == N) break; // 인덱스 마지막일 시 종료.
            if (sum >= M) sum -= inputDataArr[start++];
            else sum += inputDataArr[end++];
            // check
            if (sum == M) cnt++;
        }

        System.out.println(cnt);
    }
}