Two Pointers: 백준 부분합-1806

문제 유형: Two Pointers + Sliding Windows

부분합

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

작성 코드

import javax.sound.midi.Sequence;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int N, S;

    static int[] sequence;

    static void input() {
        N = sc.nextInt();
        S = sc.nextInt();

        sequence = new int[N+1];

        for (int i = 1; i <= N; i++) {
            sequence[i] = sc.nextInt();
        }
    }

    static void pro() {
        int R = 0, sum = 0, ans = N+1;
        for (int L = 1; L <= N; L++) {
            sum -= sequence[L-1];
            while (R + 1 <= N && sum < S) {
                R++;
                sum += sequence[R];
            }

            if (sum >= S) {
                ans = Math.min(ans, R-L + 1);
            }
        }
        if (ans == N+1) {
            ans = 0;
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        input();
        pro();
    }
}

 

접근 방식

1. input()함수로 기본적인 문제 구성에 맞춰 배열을 준비한다.

2. 두개의 포인터를 지정한다. 

• 첫번째 포인터는 순서대 진행한다.
• 두번째 포인터의 경우 순서대로 진행하나 조건을 설정한다.

3.  조건은 주어진 문제의 합을 기준으로 합에 도달할 때까지 오른쪽의 포인터는 움직인다. 합에 도달하면 그때 부터 첫번째 포인터를 이동하며 전체의 합에서 해당 숫자를 빼며 기준보다 큰 값이며 동시에 가장 짧은 거리를 찾는다. 만약 합이 기준 보다 낮아 진다면 다시 두번째 포인터를 옮겨간다.

개선 사항

1. 처음에는 투포인터를 사용했으나 N^2인 경우였다. 하지만 Sliding Window를 적용 했음에도 불구하고 실패했다. 하지만 투포인터의 핵심인 각 포인터가 움직이는 조건 그리고 한포인터가 움직이면 다른 포인터는 멈춰야한다는 핵심을 알고 있었다면 오랜 시간이 걸리지 않았을 것이다.