[BOJ-15565] 귀여운 라이언(JAVA)

백준 15565 귀여운 라이언

 

15565번: 귀여운 라이언

 

 

문제 설명

 

 - 라이언 인형과 어피치 인형 N개가 일렬로 놓여 있다.

 

 - 라이언 인형은 1, 어피치 인형은 2로 표현한다.

 

 - 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하라

 

 - 그러한 집합이 없다면 -1을 리턴하라.

---

 

입력 값

 

 - 첫 줄에 N과 K가 주어진다.(1 <= K <= N <= $10^6$)

 

 - 둘째 줄에 N개의 인형 정보가 주어진다.(1 또는 2)

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제의 조건을 살펴보면 한 가지 특징을 발견할 수 있다.

 

 - K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합 크기를 구하는 것이다.

 

 - 가장 작은 연속된 집합의 크기를 S가 하면, S+1도 K개 이상의 인형을 포함하게 되는 것이고,

   S+2, S+3, .. 등 S 이상의 크기는 모두 K개 이상의 인형을 포함한다는 것이다.

 

 - 즉, 이 문제는 파라메트릭 서치를 사용할 수 있는 조건을 가지고 있다는 것이다.

파라메트릭 서치(Parametric Search)

 

 - 집합의 최소 크기 K와 최대 크기 N 사이의 중간 값을 탐색하며 K개를 포함하는 가장 작은 집합의 개수를 찾으면 된다.

 

 - 그렇다면 중간값 MID가 주어졌을 때, 해당 집합이 K개의 인형을 포함하는지는 어떻게 판단할까?

 

 - 크기가 정해진 연속된 집합이 움직이는 것이기 때문에 슬라이딩 윈도우를 이용하여 탐색하면 O(N)의 시간복잡도로

   탐색을 할 수 있다.

투 포인터, 슬라이딩 윈도우 기법

 

 

---

 

 

소스 코드

 

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

//https://www.acmicpc.net/problem/15565
// 귀여운 라이언
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int N,K;

        StringTokenizer st = new StringTokenizer(bf.readLine());

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

        int result=Integer.MAX_VALUE;

        int dolls[] = new int[N+1];

        int start=K;
        int last=N;

        st=new StringTokenizer(bf.readLine());
        for(int i=0;i<N;i++){
            dolls[i]=Integer.parseInt(st.nextToken());
        }

        while (start<=last){
            // mid 크기의 윈도우에 k개가 있는가?
            int mid=(start+last)/2;

            int cnt[] = new int[3];

            for(int i=0;i<mid-1;i++){
                cnt[dolls[i]]++;
            }

            boolean isFind=false;

            for(int i=mid-1;i<N;i++){
                cnt[dolls[i]]++;

                if(cnt[1]>=K){
                    last=mid-1;
                    result = Integer.min(result,mid);
                    isFind=true;
                    break;
                }

                cnt[dolls[i+1-mid]]--;
            }

            if(!isFind){
                start=mid+1;
            }


        }

        if(result==Integer.MAX_VALUE){
            result=-1;
        }

        System.out.println(result);
    }
}