본문 바로가기
알고리즘/알고리즘 문제풀이

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

by E145 2021. 10. 15.
반응형

백준 15565 귀여운 라이언

 

 

15565번: 귀여운 라이언

꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의

www.acmicpc.net

 

 

문제 설명

 

 - 라이언 인형과 어피치 인형 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)

파라메트릭 서치(Parametric Search) 파라메트릭 서치란?  - 문제를 최적화 하는 방법 중 하나.  - 특정 값을 구하라는 문제(최대 값, 최소 값을 구하라)를 결정 문제로 바꿔서 생각하는 방법이다.  -

9327144.tistory.com

 

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

 

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

 

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

   탐색을 할 수 있다.

 

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

투 포인터(Two Pointers method) 투 포인터란?  - 배열을 따라 두 개의 포인터를 이동시키면서 데이터를 처리하는 알고리즘  - 포인터 두 개는 모두 한쪽 방향으로 움직인다.  - 투 포인터를 이용한 경

9327144.tistory.com

 

 


 

 

소스 코드

 

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);
    }
}

 

 

반응형

댓글