[Python] 백준 15565 귀여운 라이언 (Two Pointer)

📌 문제

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

입력

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

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

출력

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

예제 입력 1

10 3
1 2 2 2 1 2 1 2 2 1

예제 출력 1

6

---

📌 풀이

💬 Code

import sys
input = sys.stdin.readline
INF = float('inf')

n, k = map(int, input().split())
doll = list(map(int, input().split()))

size, cnt, end = 0, 0, 0
ans = INF

for start in range(n):
    while cnt < k and end < n:
        size += 1
        if doll[end] == 1:
            cnt += 1
        end += 1

    if cnt == k and ans > size:
        ans = size

    if doll[start] == 1:
        cnt -= 1
    size -= 1

print(ans if ans != INF else -1)

💡 Solution

투 포인터로 풀 수 있다.

• size: 현재 집합의 크기
• cnt: 라이언 수
• start: 집합의 시작 포인터
• end: 집합의 끝 포인터
• ans: 정답

현재 집합에서 라이언의 수가 k 미만이라면 k가 될 때까지 end를 뒤로 한 칸씩 이동시키면서 탐색을 진행한다.

라이언의 수가 k가 되었을 경우 집합의 크기를 체크한다. 이제까지의 최솟값보다 현재 집합이 가장 작은 크기를 갖는다면 정답을 업데이트한다.

더이상 end를 뒤로 이동시킬 필요가 없거나 이동시킬 수 없는 경우 start를 뒤로 한 칸씩 이동시키면서 집합의 크기를 줄여가며 더 작은 크기의 집합이 있는지 탐색을 진행한다.