백준 1806번 : 부분합 (자바)

문제

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

---

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

---

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

🔵풀이

투포인터를 활용하여 풀었습니다. 수열의 원소 하나가 S이상인 경우, 맨 마지막 수열을 포함해야 S이상이 되는경우를 예외로 처리해주었습니다. 코드가 명료하거나 명확하진 않은 것 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
    int N = Integer.valueOf(stringTokenizer.nextToken());
    int S = Integer.valueOf(stringTokenizer.nextToken());
    stringTokenizer = new StringTokenizer(br.readLine());
    int[] arr = new int[N];

    for (int i=0; i<N; i++){
      arr[i] = Integer.valueOf(stringTokenizer.nextToken());
      if (arr[i] == S) {
        System.out.println(1);
        return;
      }
    }

    int answer = Integer.MAX_VALUE;
    int one = 0;
    int two = 1;
    int sum = arr[one]+arr[two];

    while (two<N-1){
      if (sum>=S){
        answer = Math.min(answer,two-one);
        sum -= arr[one++];
      } else {
        sum += arr[++two];
      }
    }

    if (sum>=S) {
      while (sum>=S) {
        sum -= arr[one++];
        answer = Math.min(answer, two-one+1);
      }
    }

    if (answer != Integer.MAX_VALUE) {
      System.out.println(answer+1);
    } else {
      System.out.println(0);
    }
  }
}

 

그래서 큐를 활용하여 풀어보았습니다. 큐에 수열을 하나씩 넣어보며 S이상이 되면 하나씩 제거하며 S이상이 되는 최소길이를 구했습니다. 훨씬 명료하지만 시간과 메모리 측면에서는 투포인터를 활용한 풀이가 더 좋았습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
    int N = Integer.valueOf(stringTokenizer.nextToken());
    int S = Integer.valueOf(stringTokenizer.nextToken());
    int[] arr = new int[N];
    Queue<Integer> queue = new LinkedList<>();
    stringTokenizer = new StringTokenizer(br.readLine());

    for (int i=0; i<N; i++){
      arr[i] = Integer.valueOf(stringTokenizer.nextToken());
    }

    int sum = 0;
    int answer = Integer.MAX_VALUE;
    for (int i=0; i<N; i++){
      queue.add(arr[i]);
      sum += arr[i];

      if (sum>=S){
        while (sum>=S) {
          answer = Math.min(answer,queue.size());
          sum -= queue.poll();
        }
      }
    }

    if (answer==Integer.MAX_VALUE){
      System.out.println(0);
      return;
    }
    System.out.println(answer);
  }
}