[Algorithm] Two Pointers

 

 

투 포인터 알고리즘

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

 

• 1차원 배열 위에 2개의 포인터를 만드는 경우
  • 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동
  • 2개의 포인터가 양 끝에서 서로를 향해 이동
• 관찰을 통해서 문제에 등장하는 변수 2개의 값을 투 포인터로 표현하는 경우

 

 

 

투 포인터 팁

• 키워드
  • 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로" 라는 말이 있으면 한번쯤 투포인터 알고리즘을 생각해볼 필요가 있다.
  • 곱의 최소 - A x B를 최소로 하려면 A가 커지면 B가 작아져야 한다. 이 경우가 위에서 언급한 관찰을 통해서 문제에 등장하는 변수 2개의 값을 투 포인터로 설정하는 경우이다.

 

 

 

BOJ 1806 - 부분합

https://www.acmicpc.net/problem/1806

1806번: 부분합

 

• 1만 이하의 자연수로 이루어진 길이 N짜리 수열 (10 ≤ N < 10만)
• 연속된 수들의 부분합 중 그 합이 S 이상 되는 것 중, 가장 짧은 것의 길이 (0 < S ≤ 1억)
• 1 ≤ 각 원소 ≤ 1만

 

• 정답은 N이하이므로 int 범위이다.
• 모든 원소의 총합은 10^5 * 10^4 으로 총 10^9이므로 int 범위이다.

 

N=10, S=15인 경우

 

 

가장 먼저 생각할 수 있는 방법은 왼쪽 원소부터 하나씩 오른쪽 끝까지 더해서 구하는 것이다.

왼쪽 시작 원소를 L이라고 했을 때 오른쪽 끝을 R이라고 해서 L부터 R을 이동시킨다. 부분합이 S 이상을 만족하는 순간 굳이 더 오른쪽까지 탐색할 필요 없이 다음 L로 넘어간다.

 

이 방법은 시간이 O(N^2)이나 걸려서 시간 초과가 난다.

 

"연속된 수들의 부분합" 이라는 키워드가 나왔으므로 투 포인터 알고리즘으로 접근해보자

 

포인터 L과 포인터 R을 같은 곳에서 시작해서 R 포인터를 오른쪽으로 이동시키면서 부분합을 구한 후 S 이상인 경우를 확인한다. 

그런데 여기서 굳이 확인하지 않아도 되는 탐색 범위가 있다. 부분합이 S를 넘는 경우를 발견했을 때 L 포인터를 오른쪽으로 하나 이동시킨 상태에서 L부터 R을 오른쪽으로 이동시킬텐데 R을 굳이 다시 L부터 옮길 필요가 없다. 이전 경우를 통해 어짜피 S보다 작을 것이란 걸 알 수 있기 때문이다. R 포인터를 그대로 놔두고 L만 R을 따라가는 쪽으로 옮겨주면 된다. 

 

그러다가 S보다 작아질 경우 그 때 R 포인터를 S가 넘을때까지 옮겨주면 되는 것이다. 

 

따라서 정답을 위해 봐야할 부분은 다음과 같다.

 

 

L 포인터와 R 포인터는 각자 최대 N번 이동하므로 시간 복잡도는 O(N)밖에 안걸린다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, S;
    static int[] nums;

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        nums = new int[N + 1];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void pro() throws IOException {
        int R = 0;
        int sum = 0;
        // ans의 최대는 N일 것.
        int ans = N + 1;

        for (int L = 1; L <= N; L++) {
            // L-1을 구간에서 제외
            sum -= nums[L - 1];

            // R을 옮길 수 있을 때까지 옮긴 후 부분합 갱신
            while (R + 1 <= N && sum < S) {
                R++;
                sum += nums[R];
            }

            // [L~R]의 합, 즉 sum이 조건을 만족하면 정답 갱신
            if (sum >= S) {
                ans = Math.min(ans, R - L + 1);
            }

        }

        // ans 값을 보고 불가능 판단
        if (ans == N + 1) {
            bw.write("0" + " ");
        } else {
            bw.write(ans+" ");
        }

    }

    public static void main(String[] args) throws IOException {
        init();

        pro();

        bw.close();
    }

}

 

 

 

 

 

출처 : https://github.com/rhs0266/FastCampus/tree/main/%EA%B0%95%EC%9D%98%20%EC%9E%90%EB%A3%8C/02-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98