[백준] 1806, 부분합 Java

1806, 부분합

이 문제의 제한 시간은 0.5초다 (자바는 1초)

그리고 주어지는 n의 갯수는 10만이다.

따라서 O(n)이나 O(nlogn) 으로 이 문제를 풀어야 한다.

그래서 나는 O(n) 의 시간복잡도를 가지는 투 포인터를 이용하기로 했다.

다음과 같은 전략을 사용했다.

0. right가 n보다 작거나 같을 때 동안 아래 작업을 반복해준다.
1. 만약 sum이 s보다 작다면
   a. right를 1증가시키고 sum에 더해준다
2. 만약 sum이 s보다 크다면

  a. 조건에 만족하므로 answer 변수와 비교한 뒤 더 작은 수를 answer에 저장한다.

b. left를 1 증가시키고 sum에서 빼준다.

이 알고리즘을 반복한다면 answer에는 합이 s이상을 만족하는 최소의 원소 갯수가 나오게 된다.

전체 코드

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

public class Main {
    static int arr[];

    public static void main(String args[]) throws IOException {
        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());
        int s = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int answer = 987654321;
        int left = 0;
        int right = 1;
        int sum = arr[0];
        while (right <= n) {
            if (left == right)
                break;
            if (sum < s) {
                if (right == n) {
                    break;
                }
                sum += arr[right++];
            }
            if (sum >= s) {
                answer = Math.min(answer, right - left);
                sum -= arr[left++];
            }
        }
        if (answer == 987654321)
            answer = 0;
        System.out.println(answer);
    }
}