BOJ - 귀여운 라이언

15565 귀여운 라이언 : https://www.acmicpc.net/problem/15565

---

Problem

---

Solve

N개의 인형이 있고, K개의 라이언을 포함한 최소 집합 크기를 구하는 문제입니다.

먼저 start, end 포인터를 정의하고 두 포인터 사이 K개의 라이언 인형이 포함되도록 end를 이동시킵니다.
그리고 start는 범위안에서 첫번째 라이언 인형의 위치로 이동시킵니다.

K개의 라이언을 포함하는 start, end 범위가 구해졌다면, start를 그 다음 라이언이 있는 부분으로 이동시킵니다.
그렇다면 현재 범위에 K-1개의 라이언이 존재하게 되고 end를 다음 라이언이 있는 위치까지 이동시켜줍니다.

이를 반복하다가 end가 N에 도달하게 되면 더 이상 라이언을 추가할 수 없으니 반복을 종료시켜줍니다.

---

Code

public class 귀여운라이언{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int[] dolls = new int[N];

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

		int start=0;
		int end = 0;
		int lionCount = 0;
		int answer = 0;

		//lionCount가 k가 될때까지 end 이동
		while(end<N && lionCount < K){
			if(dolls[end] == 1) lionCount++;
			end++;
		}
        //첫번째 라이언 인형이 있는곳까지 start 이동
		while(start<end && dolls[start]!=1){
			start++;
		}

		//현재 범위의 라이언 개수로 초기화
		answer = end-start;
		
        //만약 라이언 개수가 K미만이라면 모든 인형을 돌았을때 라이언이 K만큼 없는것이기 때문에 반복문 제외
		if(lionCount < K) answer = -1;
		else{
			while(true){
            	/*
                K개 라면, 맨 처음 반복문에 들어온 경우 해당 분기에 들어오게됩니다.
                다음 라이언의 위치까지 start를 이동시켜주기 때문에 lionCount를 감소시킵니다.
                */
				if(lionCount >= K){
					if(lionCount == K) answer = Math.min(answer, end-start);
					lionCount--;
					start++;
					while(start<end && dolls[start] != 1){
						start++;
					}
				}else{
                	/*
                    라이언 인형 개수가 감소되었다면 end위치부터 다음 라이언이 있는 곳까지 계속 이동합니다.
                    */
					if(end>=N) break;
                    //다음 라이언 인형을 찾았다면 lionCount를 증가시켜주고 다음 반복에서 첫번째 분기로 들어가게 됩니다.
					if(dolls[end] == 1) lionCount++;
					end++;
				}
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference