두 포인터 문제 풀려고 찾아보다가 문제 제목이 귀여워서 풀게 된 문제.

BOJ 15565 - 귀여운 라이언 링크
(2022.09.29 기준 S1)
(치팅하면 안귀여워짐)

문제

라이언 인형과 어피치 인형이 섞여서 일렬로 N개 놓여 있을 때, 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기

알고리즘

크기가 K인 윈도우를 미끄러뜨리면 된다.

풀이

사실 두 포인터와 슬라이딩 윈도우를 합쳐서 푸는 방법밖에 생각이 나지 않아서 그렇게 풀려고 했는데, 막혀서 검색의 힘을 빌려서 풀어냈다.
정말 간단한 문제였다.

문제의 예제 1번을 살펴보자.

여기서 인형의 종류가 1번인 것이 라이언 인형이니깐 1번의 인덱스만 뽑아내보자.

이렇게 나오는데, 감이 오지 않는가?
라이언 인형이 K개 이상의 가장 짧은 구간을 구해야 하니깐, 라이언 인형이 K개만 있으면 된다. 그러면

파란 구간 (0-4-6), (4-6-9) 를 살펴보면 되는 것이다. 각 집합의 크기는 (end - start + 1)이 된다.

결국, 라이언 인형의 인덱스만 뽑아내서 K 크기의 윈도우를 미끄러뜨리면서 집합의 크기를 확인하는 문제였다.

코드

import sys; input = sys.stdin.readline
from math import inf

def solve():
    N, K = map(int, input().split())
    dolls = list(map(int, input().split()))

    ryan = [] # 라이언 인형들의 인덱스
    for i in range(N):
        if dolls[i] == 1:
            ryan.append(i)

    if len(ryan) < K: # K개 미만이라면 -1 출력
        print(-1)
        return

    # 크기가 K인 윈도우를 미끄러뜨리면서 답을 갱신해나가자.
    # 집합의 크기는 end - start + 1
    answer = inf
    for i in range(len(ryan) - K + 1):
        answer = min(answer, ryan[i + K - 1] - ryan[i] + 1)
    print(answer)

solve()

여담

슬라이딩 윈도우를 처음 접해보았다.
사실 두 포인터나 슬라이딩 윈도우 같은, 싹 훑는 알고리즘을 많이 접하지 않았다.
그래서 그런지 실버 문제임에도 불구하고 많이 헤맸다. 열심히 해야지..