[BOJ 15565] 귀여운 라이언 (Java, 투 포인터)

 

 

---

문제 링크

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

15565번: 귀여운 라이언

---

풀이

- 시간복잡도 O(N)

- 1 (라이언 인형) 인 경우에만 카운팅 처리를 해주고, K개이상이 되는 연속된 인형의 집합의 길이는 L, R범위로 측정

---

제출 코드

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

public class Main {
    
    static int N, K;
    static int[] A;


    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

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

    static void pro() {
        int ans = Integer.MAX_VALUE;
        int cnt = 0;
        for(int L = 1, R = 1; L < A.length; L++) {
            while(R <= N && cnt < K) {
                if(A[R] == 1) cnt += 1;

                R += 1;
            }

            if(cnt == K) ans = Math.min(ans, R - L);

            if(A[L] == 1) cnt -=1;
        }


        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }

}