백준 15565 귀여운 라이언 Python

🐸 문제 정보

15565번: 귀여운 라이언

 

🤖 알고리즘

슬라이딩 윈도우

 

⏱️ 풀이 시간

14.58m

 

📝 풀이

최근에 투포인터랑 슬라이딩 윈도우를 많이 풀어서 쉽게 풀 수 있었다.

1. start = 0, end = k로 시작한다. (어차피 k개는 필수로 들어가야하기 때문)
2. 이때 사이에 있는 1의 값은 미리 카운트하여 선언한다.
3. end가 n이 될 때까지 아래 조건에 따라 인덱스를 움직이며 계산한다.
   
   • 1의 개수가 k개와 같다면
     • 현재 거리를 res와 비교하여 최솟값으로 저장한다
     • start 인덱스에 있던 인형이 1이었다면, start를 움직이며 카운트를 1 감소한다
     • 아니라면 그냥 start를 움직인다.
   • 1의 개수가 k개 보다 작다면
     • end를 뒤로 한 칸 움직일건데, 움직인 곳에 1이 있다면 카운트에 1을 더한다.
   • 1의 개수가 k개 보다 크다면
     • start 인덱스에 있던 인형이 1이었다면 start를 움직이며 카운트를 1 감소한다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline
INF = sys.maxsize

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

start = 0
end = k
cnt = dolls[start:end + 1].count(1)
res = INF

while end != n:
    if cnt == k:
        res = min(res, end - start + 1)
        if dolls[start] == 1: cnt -= 1
        start += 1
    elif cnt < k:
        end += 1
        if (end < n) and (dolls[end] == 1): cnt += 1
    else:
        if dolls[start] == 1: cnt -= 1
        start += 1

if res == INF:
    print(-1)
else:
    print(res)