[백준/14465] 소가 길을 건너간 이유 5 - JAVA

📌 문제

알고리즘 분류 : 누적합, 투포인터
난이도 : 실버2
출처 : 백준 - 소가 길을 건너간 이유 5

🦧 문제 풀이 접근

크기가 N인 배열을 선언 후 신호등이 부서진 index에는 0, 부서지지 않은 index에는 1을 넣음.
시작index와 끝index에 각각 0, K-1 값을 넣음
0 ~ K-1 까지의 0의 갯수를 구한 후, 1씩 커지면서 모든 0의 갯수 중 최소 값을 구함.

💻 code

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

public class Main {

    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 K = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        Integer[] brokeArr = new Integer[N];
        for(int i=0;i<N;i++) {
            brokeArr[i] = 1;
        }
        for(int i=0;i<B;i++) {
            brokeArr[Integer.parseInt(br.readLine())-1] = 0;
        }
        int f = 0, b = K-1;
        int brokeCnt = 0;
        for(int i=0;i<=K-1;i++) {
            if(brokeArr[i] == 0) brokeCnt++;
        }
        int minCnt = brokeCnt;
        while(b<N-1) {
            if(brokeArr[f]==0)
                brokeCnt--;
            f++;
            if(brokeArr[++b]==0)
                brokeCnt++;
            minCnt = Math.min(minCnt,brokeCnt);
        }
        System.out.println(minCnt);
    }

}

🥇 결과

🎓 느낀점

투포인터 문제와 누적합 문제의 콜라보레이션