백준 15565 귀여운 라이언 Kotlin (투 포인터)

문제 출처 : https://www.acmicpc.net/problem/15565

15565번: 귀여운 라이언

문제

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

입력

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

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

출력

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

알고리즘 분류

• 두 포인터

풀이

투 포인터 문제다.

슬라이딩 윈도우를 똑같이 구현하면 된다고 생각하면 된다.

왼쪽 끝은 라이언이 시작하는 지점-1, 오른쪽 끝은 계속 한 칸씩 오른쪽으로 움직인다.

왼쪽 끝을 s, 오른쪽 끝을 e라고 하자.

바깥 포문은 e를 0부터 하나씩 늘리면서 '1'의 개수를 체크해 준다.

만약 s< x <=e 사이에 '1'이 k이상 있다면 s를 늘려주며 최소 길이를 갱신한다.

위의 개념만 제대로 구현한다면 통과할 수 있기 때문에 반례를 생각하는 것보다 위 로직을 제대로 구현하는 것에 집중하자.

주의할 점은 K개 이상의 라이언을 포함한 슬라이딩 윈도우를 만들 수 없다면 -1을 출력한다. 

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n,k) = getIntList()
    val tk = StringTokenizer(br.readLine())
    val input = IntArray(n+1){if(it==0) 0 else tk.nextToken().toInt()}
    var answer = Int.MAX_VALUE
    var cnt = 0
    var s = 0
    //solve
    for (e in input.indices) {
        if (input[e] == 1) cnt++
        if (cnt >= k) answer = answer.coerceAtMost(e - s + 1)

        while (cnt >= k && s < e) {
            s++
            answer = answer.coerceAtMost(e - s + 1)
            if(input[s] == 1) cnt--
        }
    }
    //output
    write("${if (answer == Int.MAX_VALUE) -1 else answer}")
    close()
}