[Baekjoon 1806] 부분합 - JAVA

[Gold IV] 부분합 - 1806

문제 링크

성능 요약

메모리: 23708 KB, 시간: 300 ms

분류

누적 합, 두 포인터

문제 설명

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

입력

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

출력

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

문제 풀이

문제의 핵심은 시간초과가 발생하지 않도록 O(N)의 시간 복잡도 알고리즘을 찾는것이다.

필자는 투 포인터로 풀었지만 구현, 이분탐색, 큐 등 다양한 방식으로 풀 수 있을것 같다.

투 포인터 문제는 인덱스 범위만 신경쓰면 그리 어렵지 않게 풀 수 있다.

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

public class Main {
    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());
        int[] numbers = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        int left = 0, right = 0, minLength = N + 1, currentSum = numbers[0];
        while (right < N && left <= right) {
            if (currentSum >= S) {
                minLength = Math.min(minLength, right - left + 1);
                currentSum -= numbers[left++];
            } else {
                right++;
                if (right < N) {
                    currentSum += numbers[right];
                }
            }
        }

        if (minLength > N) {
            minLength = 0;
        }

        bw.write(String.valueOf(minLength));
        bw.newLine();
        bw.flush();

        br.close();
        bw.close();
    }
}

코드 풀이

public class Main {
    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());
        int[] numbers = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

• N: 입력으로 받은 배열의 크기를 나타내는 변수
• S: 부분 배열의 합이 되어야 하는 목표값을 나타내는 변수
• numbers: 입력으로 받은 숫자들을 저장하는 정수 배열

int left = 0, right = 0, minLength = N + 1, currentSum = numbers[0];
while (right < N && left <= right) {
    if (currentSum >= S) {
        minLength = Math.min(minLength, right - left + 1);
        currentSum -= numbers[left++];
    } else {
        right++;
        if (right < N) {
            currentSum += numbers[right];
        }
    }
}

• left, right: 현재 부분 배열의 시작과 끝을 가리키는 인덱스
• minLength: 최소 길이를 저장하는 변수
• currentSum: 현재 부분 배열의 합을 나타내는 변수
• while 루프는 right가 배열의 끝에 도달하지 않았고, left가 right보다 크지 않을 동안 계속 실행된다.
• 현재 부분 배열의 합이 S 이상이면 최소 길이를 업데이트하고, left를 오른쪽으로 이동시켜 부분 배열의 시작을 이동시킨다.
• 그렇지 않으면 right를 오른쪽으로 이동시키고, 만약 배열의 끝이 아니라면 currentSum에 새로운 숫자를 더한다.

if (minLength > N) {
    minLength = 0;
}

bw.write(String.valueOf(minLength));
bw.newLine();
bw.flush();

br.close();
bw.close();

• 만약 minLength가 초기 값인 N + 1과 같다면, 합을 만족하는 부분 배열을 찾지 못한 것이므로 minLength를 0으로 설정한다.
• 그렇지 않으면 minLength를 출력한다.