자바(백준) 15565 귀여운 라이언

오답 노트 & 새로 알게 된 점

1의 개수가 K개 만큼 있을 때, 집합의 개수를 최소화시켜야한다.

이 때에는 e를 늘리면서 1을 만나게 되면 cnt++을 해주고, 개수를 만족시키면 s를 한칸씩 밀면서(배열에서 빼면서) 온다.

이 때, 배열에서 뺄 때 1을 빼게 된다면 cnt--을 해줘야한다.

투 포인터 기본 문제이다.

 

---

 

코드

package TwoPointers;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ15565 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, K;
    static int A[];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        K = atoi(st.nextToken());
 
        A = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
 
        for (int i = 1; i <= N; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        pro();
    }
 
    static void pro() {
        int e = 0, rel = N+1, cnt = 0;
 
        for (int s = 1; s <= N; s++) {
            if(A[s-1] == 1){
                cnt--;
            }
 
            while (e + 1 <= N && cnt < K) {
                if(A[++e] == 1) cnt++;
            }
 
            if(cnt == K) rel = Math.min(rel, e - s + 1);
        }
 
        if(rel == N + 1) rel = -1;
 
        System.out.println(rel);
    }
}