[백준 JAVA] 투포인터 모아풀기

 

마이다스 코테를 준비하면서 예전에 있던 문제들을 다시 풀어보았는데 투포인터에서 항상 막히고 못푸는 모습을 보였다.

관련 문제들을 풀면서 이번기회에 제대로 한번 개념을 잡고가보도록 하자.

 

우선 투포인터란

투 포인터(two pointers)는 배열에서 두 개의 인덱스를 이동시키며 조건을 만족하는 구간을 찾는 기법이다.
주로 연속된 부분 배열 문제에서 사용되며, 이중 반복문을 O(N)으로 줄이기 위해 활용한다.

핵심은 포인터가 한 방향으로만 이동한다는 점이다.
왼쪽 포인터와 오른쪽 포인터는 각각 최대 N번 이동하므로 전체 시간 복잡도는 O(N)이다.

 

연속 부분합 문제에서 투 포인터의 기본 구성은 다음과 같다.

• l: 구간 시작 인덱스
• r: 구간 끝 인덱스 (보통 포함하지 않음)
• sum: 현재 구간의 합

구간의 합(sum)을 유지하면서 조건에 따라 구간을 늘리거나 줄인다.

 

투 포인터 구현에서 가장 중요한 것은 조건 분기 순서다.

• 구간을 늘리는 동작(r 이동)은 항상 경계 체크가 필요하다
• 구간을 줄이는 동작(l 이동)은 상대적으로 안전하다

 

투 포인터 문제를 풀기 전 정리할 질문은 다음 정도면 충분하다.

• 연속된 구간을 다루는 문제인가?
• 구간 길이는 고정인가, 가변인가?
• 구간을 늘리는 조건과 줄이는 조건은 무엇인가?
• r이 끝에 도달했을 때 종료 조건은?

이제 문제를 풀어보도록 하겠다.

 

2003번: 수들의 합 2

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

 

문제 요약 : N개의 수로된 수열 (1 <= N <= 10,000) 에 연속된 부분수열의 합이 M이 되는 경우를 구하는 문제이다.

 

접근 방법 : 연속 부분 배열 문제이므로 투포인터를 사용했다. 포인터를 한 방향으로 이동시켜 O(N)에 해결한다.

 

풀이 전략 :

1. 처음엔 sum을 0으로 초기화하고 

2. 합이 M 보다 크거나 같으면 우선 먼저 처리해준다. 같을때만 정답을 늘려주고 start를 빼준다.

3. 그 다음 end 부분이 N 까지 도달했다면 

 

시간복잡도 : O(N)

 

코드 : 

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

public class Main {
    static int N, M, ans;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        ans = 0;

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0, end = 0, sum = 0;
        while(true){
            if(sum >= M){
                if(sum == M) ans++;
                sum -= arr[start++];
            }else if(end == N){
                break;
            }else{
                sum += arr[end++];
            }
        }

        System.out.println(ans);
    }
}

 

회고

항상 이런 문제를 보면 우선 누적합을 이용하여 N^2에 문제를 풀려고 했는데 투포인터를 활용하는 방식을 머리속에 넣은것같다.

 

2559번: 수열

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

 

문제 요약 : 음수가 섞여있는 온도 N개의 수열에서 연속적인 K일의 구간합이 최대가 되는 값을 출력하는 문제이다.

 

접근 방법 : 이 문제는 고정 길이의 연속 구간을 다루므로 누적합으로 해결할 수 있으며 동일한 로직을 슬라이딩 윈도우 형태의 투 포인터로도 구현할 수 있다.

 

풀이전략 :
1. 누적합 배열을 만든다.

2. K 만큼 떨어진 곳의 차를 이용하여 구간합을 구한다.

3. 그 중 최대값을 ans 에 저장 후 출력한다.

 

시간복잡도 : O(N)

 

코드 : 

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

public class Main {
    static int N, K, ans;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new int[N + 1];
        ans = Integer.MIN_VALUE;

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

        for(int i = K; i <= N; i++){
            int sum = arr[i] - arr[i - K];
            ans = Math.max(sum, ans);
        }

        System.out.println(ans);
    }
}

 

회고 : 누적합을 바로 떠올리긴 했지만 구간설정에 조금 시간이 걸렸다. 배열을 0부터 안쓰고 1부터 쓰는건 편한거같다.

 

1644번: 소수의 연속합

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

 

문제 요약 : 주어지는 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제

 

접근 방법 : 먼저 에라토스테네스의 채로 소수들을 구한 뒤 투포인터를 활용하여 N 이 되는 경우의 수를 구한다.

 

풀이전략 :

1. 에라토스테네스의 채를 사용하여 배열에 소수들을 차례대로 채워놓는다.

2. 투포인터를 활용하여 sum = 0에서 N보다 크거나 같으면 start를 줄이고 그중 N과 같다면 ans증가

3. sum이 N보다 작으면 리스트의 마지막에 end가 도달했는지 확인 후 늘리기

 

시간복잡도 : O(N)

 

코드 : 

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

public class Main {
    static int N, ans;
    static int[] isPrime;
    static List<Integer> list;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();
        isPrime = new int[N + 1];
        ans = 0;

        // 1. 소수 리스트 만들기
        Arrays.fill(isPrime, 1);
        isPrime[0] = 0;
        isPrime[1] = 0;

        for(int i = 2; i * i <= N; i++){
            if(isPrime[i] == 1){
                for(int j = i * i; j <= N; j += i){
                    isPrime[j] = 0;
                }
            }
        }

        for(int i = 2; i <= N; i++){
            if(isPrime[i] == 1) list.add(i);
        }

        // 2. 연속된 구간합 파악
        int start = 0, end = 0, sum = 0;
        while(true){
            if(sum >= N){
                if(sum == N) ans++;
                sum -= list.get(start++);
            }else{
                if(end == list.size()) break;
                sum += list.get(end++);
            }
        }

        System.out.println(ans);
    }
}