[BOJ] 1806번 - 부분합 (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

start : 현재 누적합의 시작 인덱스
end : 현재 누적합의 끝 인덱스
sum : nums[start] + .... + nums[end] 의 합

sum 이 s 이상이면 (end - start + 1) 수열의 길이 비교
sum이 s 초과이면 start++ 하여 sum 감소시키기
아니면 end++ 하여 sum 증가시키기
단, end == n이 되는 순간 배열의 범위를 넘어갔기 때문에 중단해주기!

 

위의 설명을 나의 풀이이다.

이 문제를 풀면서 end가 n이 되는 순간의 예외처리를 잘못해서 계속 틀렸었다.

그래서 다른 사람의 풀이를 참고하다 보니 나와 다른 점이 있어서 이를 기록하다.

 

다른 사람의 풀이에서는 

start부터 end-1 인덱스까지의 합을 누적합으로 보았다.

그래서 이때 필요한 처리 중 하나가 수열의 배열의 크기를 n이 아닌 n+1로 선언해주어야한다는 것이다.

5 15
1 2 3 4 20

 

위와 같이 입력이 들어올 경우 정답은 1이다.

그러나 만약 배열의 크기를 n으로 선언하면 마지막 인덱스 값까지 탐색을 할 수 없어 0으로 출력된다.

즉, start가 4에 있으면 end는 5에 있어야 누적합이 20이 되기때문이다.

 

그래서 처음에는 나도 위와 같이 처리를 안해주어서 틀렸나 해보았는데 나에게는 올바른 해결책이 아니었다.

하지만 이러한 방식으로 예외처리가 필요할 수 있다는 것을 알았다.

 

우선 문제를 꼼꼼히 보고 나의 상황을 올바르게 이해해 이를 해결해 나가야겠다. 

---

🍀 풀이 🍀

package Baekjoon;

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

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

        System.out.println(minLength(nums, s));
    }

    public static int minLength(int[] nums, int target) {
        int answer = Integer.MAX_VALUE;

        int start = 0;
        int end = 0;
        int sum = nums[0];
        while(start < nums.length && end < nums.length) {
            if(sum >= target) {
                answer = Math.min(answer, end - start + 1);
            }
            if(sum > target) {
                sum -= nums[start];
                start++;
            }
            else {
                end++;
                if(end == nums.length) {
                    break;
                }
                sum += nums[end];
            }
        }
        
        if(answer == Integer.MAX_VALUE) {
            answer = 0;
        }
        return answer;
    }
}