[백준 15565] 귀여운 라이언 (자바)

백준 15565번 귀여운 라이언 (자바)

 

 

 

출처

www.acmicpc.net/problem/15565

15565번: 귀여운 라이언

 

 

문제

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

 

 

 

입력

첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 10^6)

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

 

 

 

출력

K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력한다. 그런 집합이 없다면 -1을 출력한다.

 

 

 

 

입출력 예

입출력 예1

 

 

걸린 시간

 

 

접근 방법

투포인터 공식을 그대로 사용했더니 시간 초과가 났다.

N과 K의 범위가 10^6이기 때문에 최악의 경우 O(N^2)이 될 수 있기 때문에 안되었던 것 같다.

 

때문에 도저히 가지치기 할 곳이 보이지 않아 해결방법을 계속 생각하던 중 라이언만 따로 list에 담아서 하면 복잡도가 많이 줄어들 것이라 생각하여 list에 담고 그 라이언들만 투 포인터에 사용했다.

 

k개 이상일 때, 가장 작은 집합의 크기를 구해야 하므로 개수를 세는 cnt와 범위에 필요한 start와 end를 사용했다.

 

end가 list범위를 넘지 않고, cnt가 K를 넘지 않으면 아직 조건에 충족하지 못한 것이므로 cnt와 end를 1씩 증가시켰다.

 

그 후, cnt가 k와 같아지면 start와 end의 인덱스 번호를 빼서 거리를 구해주었다.

 

 

 

내 코드

 

 

고려할 점

1. 투 포인터 사용!

2. 시간 복잡도 생각할 것

3. 라이언만 따로 list에 담을 것