[백준 - 1806번] 부분합 - Java //Wello Horld//

이번에는 백준 알고리즘의 1806번 문제, "부분합"을 풀어보도록 하자

일단 이번 문제에서 입력은 수열의 길이 N 과 연속된 수들의 합의 판단기준이 될 S 가 주어지고, 두번째 줄에는 해당 수열이 주어진다. 출력으로는 부분합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 출력하면 된다. 문제 설명 자체는 간단하지만, 과정이 살짝 복잡해 보인다.

이번 문제에서 사용되는 알고리즘은 투포인터이다. 투포인터 알고리즘이란, 두개의 포인터를 두고 그 포인터들을 이동 시키면서 답을 구해나가는 과정이다. 밑에 그림을 보면서 이해해 보도록 하자. 일단, 예제에서 주어진 것과 같이 

• N = 10 S = 15
• 수열 : 5 1 3 5 10 7 4 9 2 8

이 있을때, 처음위치(0)인 부분에 두개의 포인터를 놔둔다.(sum은 포인터 두개 사이의 원소합이다)

이후에, second포인터를 오른쪽으로 옮기면서 문제에서 주어진 S값보다 커질 때까지, sum(부분합)을 구해 나간다.

이때, sum(부분 합)의 값이 문제에서 주어진 S(15) 보다 커지므로, second포인터를 오른쪽으로 옮기는 과정을 잠깐 멈춘다. 이번문제에서 구하고 싶은 것은 S보다 큰 부분합중에 길이가 가장 작을 때를 구하는 것이므로, 이번에는 first포인터를 오른쪽으로 옮기면서 부분합이 S보다 작을 때까지, 부분합이 S보다 큰지 판단 해준다.

sum(부분합)이 S보다 작아졌으므로, 다시 second포인터를 오른쪽으로 옮겨 볼까요?

다시, 부분합이 S보다 커졌으므로, first포인터를 오른쪽으로 옮깁니다.

다시, sum(부분합)이 S보다 작아졌으므로,

다시, 부분합이 S보다 커졌으므로, first포인터를 오른쪽으로 옮깁니다. 이 이후부터의 설명은 생략할게요

드디어, second포인터를 마지막 까지 가져왔네요. second포인터가 수열의 크기 N인 지점에 위치하게 되면, 두가지 방법으로 알고리즘을 처리할 수 있어요. 일단, first포인터를 S보다 작을때까지 오른쪽으로 옮겨줍니다.

 이때, 그냥 루프를 벗어나줘도 됩니다. 왜냐하면, 어처피 first포인터를 오른쪽으로 옮겨주더라도, 부분합이 S보다 커질 수가 없기 때문입니다. 그런 예외 처리를 해주기 싫으시다면 그냥, 앞에서 한 것과 같이 first포인터를 오른쪽으로 옮겨서 first포인터가 N이 되었을때, 루프를 닫아주셔도 됩니다. 하지만, 전자가 조금이라도 효율이 좋겠죠?ㅎㅎ

위와같이 투포인터를 이용해서 답을 구해보면, first포인터와 second포인터 사이의 원소가 가장 최소가 되는 부분합이 S이상일 떄는, [5, 10] 과 [10, 7] 일 때이고, 그리므로 답은 2가 되겠네요. 이 알고리즘의 시간복잡도는 O(N)으로 낮습니다. 위에 설명만 보면 복잡한 것 같지만, second포인터를 오른쪽으로 옮기는게 N번 first포인터를 오른쪽으로 옮기는게 최대 N번으로 (2*N)번만에 답을 구할 수 있기 때문입니다.

생각보다 어렵지는 않죠?

성공한 코드는 아래에 첨부할게요

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

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        long S = Long.parseLong(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] Narr = new int[N];
        for(int i = 0; i < N; i++){
            Narr[i] = Integer.parseInt(st.nextToken());
        }
        int ans = 100001, sum = 0;
        int firstPointer = 0, secondPointer = 0;
        while(true){
            if(sum >= S){
                sum -= Narr[firstPointer++];
                ans = Math.min(ans, (secondPointer - firstPointer) + 1);
            }
            else if(secondPointer == N) break;
            else sum += Narr[secondPointer++];
        }
        if(ans == 100001){
            bw.write(0 + "\n");
        } else {
            bw.write(ans + "\n");
        }
        
        bw.flush();
        br.close();
        bw.close();
    }
}