[Algorithm] 백준 투포인터 문제 - 부분합(1806) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 투포인터 문제 부분합 자바 풀이를 진행하고자 합니다.

 

문제 출처: https://www.acmicpc.net/problem/1806

1806번: 부분합

 

1. 풀이 소스

 

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

import static java.lang.Integer.parseInt;

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

        int n = parseInt(st.nextToken());
        int s = parseInt(st.nextToken());
        PartialSum ps = new PartialSum(n, s);

        st = new StringTokenizer(br.readLine());
        for (int i = 0 ; i < n; i++) {
            ps.setMap(i, parseInt(st.nextToken()));
        }

        ps.run();
        System.out.println(ps.getResult());
    }
}

class PartialSum {
    int n;
    int target;
    int result = Integer.MAX_VALUE;
    int[] map;

    public PartialSum(int n, int target) {
        this.n = n;
        this.target = target;
        map = new int[n + 1];
    }

    void setMap(int i, int value) {
        map[i] = value;
    }

    void run() {
        int length = 0;
        int sum = 0;
        int left = 0;
        int right = 0; 

        while (left <= n && right <= n) {
            if (sum < target) { // 타겟이 더 큰 경우
                sum += map[right++]; // 값을 더한 후, 오른쪽 포인터 한 칸 증가  
            } else {
                sum -= map[left++]; // 현재 있는 값 빼고 왼쪽 포인터 한 칸 증가  
                length = right - left + 1; 
                result = Math.min(length, result);
            }
        }
    }

    int getResult() {
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

// 순서
// 포인터에 위치한 값을 처리하고 포인터 이동
// sum이 target보다 크거나 같다면,
// sum에서 left포인트 값 빼고, left 이동 시킴
// 그 후 right - left한 후 + 1 (개수 이므로)

// sum이 target보다 작다면
// sum에서 right값을 더하고 포인터 이동

// 0 1 2 3 4
// 0     0
//

// target = 3
// p: 1, 3,  sum : 1 + 2
// p: 2, 3   sum : 2    --> length = 3 - 2 + 1
// p: 2, 3 sum(2)

 

 

2. 풀이 중점 사항

 

자연수로된 부분합 문제의 큰 특징은 단조 증가라는 것입니다.

예를 들어, 1, 3, 5, 3, 7 이 있을 때,

시작 수열의 인덱스가 1이고, 끝 인덱스가 3이라고 가정하겠습니다.

그렇다면 합은 3, 5, 3 이 됩니다.

여기서 합을 늘리는 방법은 두가지가 있습니다.

시작 인덱스를 -- 하거나, 끝 인덱스를 ++ 하는 방법입니다.

 

만약 합 12를 만족하는 가장 짧은 연속된 수열을 선택하는 경우가 생긴다면 다음과 같이 선택할 수 있습니다.

5, 3, 7 입니다.

 

투포인터를 활용한다면

1 

s

e                      (12 보다 작으므로 e 포인터 1 증가)

 

1    3

s    e                (12 보다 작으므로 e 포인터 1 증가)

 

1    3    5

s          e            (12 보다 작으므로 e 포인터 1 증가)

 

1    3    5    3

s                 e     (12를 만족하므로 s포인터를 1 증가)

 

3    5    3

s           e         (12 보다 작으므로 e 포인터 1 증가, s를 감소시키지 않은 이유는 이전에 s가 1일 때를 이미 했으므로 (무한 루프 방지))

    

3    5    3    7

s                e    (12를 만족하므로 포인터 s 1 증가)

 

5       3       7

s                e   (12를 만족하므로 포인터 s 1 증가)

 

3       7 

s       e          (12 보다 작으므로 e 포인터 1 증가 --> 인덱스 끝이므로 더 이상 단조 증가 불가 -> 종료)

 

처럼 해결할 수 있습니다.

 

while (left <= n && right <= n) {
    if (sum < target) { // 타겟이 더 큰 경우
        sum += map[right++]; // 값을 더한 후, 오른쪽 포인터 한 칸 증가
    } else {
        sum -= map[left++]; // 현재 있는 값 빼고 왼쪽 포인터 한 칸 증가
        length = right - left + 1;
        result = Math.min(length, result);
    }
}

 

따라서, 만약 타깃보다 값이 작다면 right를 증가시키고,

타깃보다 값이 같거나 크다면 left를 증가시키는 방법으로 문제를 해결할 수 있습니다.

 

이상으로 투포인터 부분합 자바 풀이를 마치도록 하겠습니다. 감사합니다.!