문제 설명

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

입력 조건

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

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

출력 조건

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

전체 코드

import sys

n, k = list(map(int, sys.stdin.readline().split()))

arr = list(map(int, sys.stdin.readline().split()))

answer = sys.maxsize

left = 0
right = 0

# 라이언 인형의 개수
one = 0

if arr[left] == 1:
    one += 1

# 왼쪽 포인터, 오른쪽 포인터 둘 중 하나가 끝에 도달할 때까지 반복한다.
while left < len(arr) and right < len(arr):
    # 라이언 인형의 개수가 부족하다면, 오른쪽 포인터를 옮겨 본다.
    if one < k:
        right += 1
        if right < len(arr) and arr[right] == 1:
            one += 1
    # 라이언 인형의 개수가 충분하다면, 왼쪽 포인터를 옮겨 본다.
    else:
        # 딱 맞게 되있다면, 사이즈를 찾아 놓는다.
        if one == k:
            answer = min(answer, right - left + 1)

        if left < len(arr) and arr[left] == 1:
            one -= 1
        left += 1

if answer == sys.maxsize:
    print(-1)
else:
    print(answer)

n이 최대 10^6인 배열에 대한 문제이기 때문에 아무리 느려도 O(nlogn)으로 풀어야 하는 문제이다. 따라서 n^2 풀이인 브루트 포스 등은 활용할 수 없다.

문제의 힌트는 '연속된' '집합의 크기'였다. 배열 문제에서 연속된 구간을 사용하는 알고리즘은 '투 포인터'가 있다. 그리고 '투 포인터'의 경우 O(n) 풀이가 가능하기 때문에 위 문제에 적용해도 시간 초과가 나지 않는다.

느낀 점

입력 예시가 이해가 안갔던 문제이다. 알고리즘 분류를 보고 풀었기 때문에 쉽게 풀었지, 유형 분류를 모르고 풀었으면 못 풀었을 문제이다. 복습할 필요가 있다.