[백준] 15565번: 귀여운 라이언

문제

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

입력

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

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

출력

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

입출력 예제

풀이

투 포인터 알고리즘을 사용한 풀이

두 개의 포인터 start와 end를 사용하여 인형 배열을 탐색한다.
처음에 두 포인터와 라이언 인형의 개수 count를 0으로 설정한다.
start 포인터가 배열의 끝에 도달할 때까지 다음과 같은 로직을 반복한다.

count가 K 미만이고 end가 배열의 끝을 넘지 않을 때,
end 위치의 인형이 라이언 인형이면 count를 1 증가시킨다.
그리고 end를 1 증가시킨다.

그렇지 않으면 start 위치의 인형이 라이언 인형이라면 count를 1 감소시키고,
start를 1 증가시킨다.
count가 K 이상이면, 현재 start와 end 사이의 길이와 기존의 answer 중
작은 값을 answer에 저장한다.

마지막으로 answer가 초기값과 같다면 -1을 출력하고, 그렇지 않다면 answer를 출력한다.

import sys
input = sys.stdin.readline

N, K = map(int, input().split(" "))
dolls = list(map(int, input().split(" ")))


def solution(N, K, dolls):
    answer = N + 1
    start, end = 0, 0
    count = 0
    while start < N:
        if count < K and end < N:
            count += 1 if dolls[end] == 1 else 0
            end += 1

        else:
            count -= 1 if dolls[start] == 1 else 0
            start += 1

        if count >= K:
            answer = min(answer, end - start)

    print(answer if answer != N + 1 else -1)
    return


solution(N, K, dolls)