❤️[백준] 1806 부분합 java

1. 문제 설명 📌

https://www.acmicpc.net/problem/1806

 

문제가 직관적이라 설명 생략!

2. 접근 방식 🗃️

KEY WORD: TWO POINTER

1. 목표값 보다 Two Pointer 구간 내의 합이 작으면 오른쪽 포인터 이동
2. 목표값 보다 크거나 같으면 왼쪽 포인터 이동
3. 구간 내 합이 목표값 이상이면 Math.min(이전까지의 최소 개수, 현재 개수)로 최소값 갱신

3. 코드 소개 🔎

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

public class Main {

    /*
    * KEY WORD: 투 포인터
    * 1. 목표값보다 작으면 오른쪽 포인터 이동
    * 2. 목표값보다 크거나 같으면 왼쪽 포인터 이동
    * 3. 목표값과 일치하면 그 개수를 뽑아내서 최소값인지 확인 후 갱신
    * */

    public static void main(String[] args) throws IOException {
        int answer = Integer.MAX_VALUE;
        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 [] arr = new int [N+1];

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

        int left = 0;
        int right = 1;
        int acc = arr[1];
        while(left < N + 1 && right < N + 1){
//            System.out.printf("left: %d. right: %d, 현 acc: %d\n", left,right,acc);
            if(acc < S) {
               right++;
               if(right >= N + 1) break;
               else acc += arr[right];
            }
            else {
                answer = Math.min(answer, right - left + 1);
                acc -= arr[left++];
            }
        }
        if (acc >= S) {
            answer = Math.min(answer, right - left + 1);
            acc -= arr[left++];
        }

        System.out.println(answer == Integer.MAX_VALUE? 0 : answer);
    }
}

4. 배운 것들 🎯

프로그래머스와 백준을 번갈아 푸니, 각자 문제를 내는 방식이 다른 것 같다. 백준은 꼬는 것 없이 알고리즘만 알면 풀리기 때문에 더 쉬운 것 같다. 예전에 프로그래머스 Lv2가 백준 실버라는 말이 있었는데, 그런 것은 옛말인 것 같다. 프로그래머스 Lv2가 백준 골드 4,5보다 어렵다.