[백준] 1806번 부분합 for JAVA - 인덱스 이동

문제설명

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

 

제한사항

입력

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

 

출력

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

 

 

문제풀이

이번 문제는 이중 for문을 적용할 경우, 시간초과에 걸리는 문제입니다. 

따라서 연속된 수열의 시작점(left)과 끝점(right)을 인덱스로 지정하여 순차적으로 계산하면 시간복잡도를 줄일 수 있습니다.

로직은 간단합니다.

부분합이 S이상이 되는지 확인하고 S 이상이라면 끝점을 오른쪽(right)으로 +1만큼 이동시키고, S 미만이라면 시작점(left)를 +1 만큼 이동시킵니다. 만약 끝점이 N보다 크거나 같다면 반복을 종료합니다.

 

• 변수 설명
  • res : 부분합의 최소 길이
  • right : 부분합의 오른쪽을 나타내는 인덱스
  • left : 부분합의 왼쪽을 나타내는 인덱스
  • sum : 계산한 부분합

 

• 로직
  • sum < S 이면, sum에 right번째 값을 더하고 right를 오른쪽으로 한 칸 이동
  • rigth >= N이면, 반복문에서 빠져나옴
  • sum >= S 이면, res를 최소값으로 저장 sum에서 left번째 값을 빼고 left를 오른쪽으로 한 칸 이동

 

💡 Solution

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

public class Main {

	static StringTokenizer st;
	static int N, S, input[];
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());

		input = new int[N];
		st = new StringTokenizer(br.readLine(), " ");
		for (int n = 0; n < N; n++) {
			input[n] = Integer.parseInt(st.nextToken());
		}
		int res = Integer.MAX_VALUE;
		int left = 0, right = 0, sum = 0;

		while (true) {
			if (sum >= S) {
				if (res > (right - left)) {
					res = right - left;
				}
				sum -= input[left++];
			} else if (right >= N) {
				if (res == Integer.MAX_VALUE)
					res = 0;
				break;
			} else {
				sum += input[right++];
			}
		}
		System.out.println(res);
		br.close();
	}

}

 

마치며

처음에는 이중 for문으로 구현했으나 역시나 O(N^2)의 시간복잡도를 가져 시간초과에 걸렸습니다. 

이에 인덱스를 이용하여 왼쪽, 오른쪽 포인터를 이동하는 방식으로 구현하였습니다.

결과적으로 O(N)의 시간복잡도를 가지는 로직을 구현할 수 있었습니다.

 

문제 바로가기

1806번: 부분합