[백준] 귀여운 라이언 (JAVA)

문제 풀러가기

문제

난이도: 실버 1

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

---

문제 분석

문제 읽자마자 생각나는 풀이방법, 두 포인터 or 슬라이딩 윈도우

바로 기본 두 포인터 방법으로 시도해봤는데 바로 시간초과가 났다
입력 값 범위를 보면 훠우.. 그럴만 한듯

그래서 이 문제는 서치를 좀 해봤다..

---

풀이 방법

라이언 인형이 K개 이상 있는 가장 작은이므로 결국 라이언 인형은 K개면 된다..
이게 이 문제의 함정이었다

저 부분을 인지하고 슬라이딩 윈도우 알고리즘을 적용해서 해결할 수 있는데,
먼저 라이언의 위치를 받아 놓고 K개 만큼 이동하며 가장 작은 차를 구하는 것!
왜냐 위치의 차는 right-left+1을 하면 나오니까~!

---

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/*
 * 라이언 1, 어피치 2로 표시
 * 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합 크기를 구하여라
 * 두 포인터는 시간초과 남
 * -> 라이언 인형이 K개 이상 있는 가장 작은이므로 결국 라이언 인형은 K개면 된다..
 * 이 문제의 함정이었음..
 * 슬라이딩 윈도우로 해결 가능 - 라이언의 위치를 받아 슬라이딩 윈도우
 */

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[N];
		List<Integer> lion = new ArrayList<>();
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			if(arr[i]==1) lion.add(i);
		}
		//입력 완료
		
		int answer = Integer.MAX_VALUE;
		if(K>lion.size()) answer = -1;
		else {
			int left = 0, right = K-1;
			
			while(right<lion.size()) {
				answer = Math.min(answer, lion.get(right)-lion.get(left)+1);
				
				left++;
				right++;
			}
		}
		
		System.out.println(answer);
	}

}

오호호 여전히 결론은 문제를 잘 읽자!