[백준] 11577번 Condition of deep sleep (Python)

백준 11577 Condition of deel sleep

여러분 접했던 문제라 생각하고 풀었다가 시간 초과의 늪에서 헤맨 문제다. 그리디 알고리즘을 활용해서 풀어야 하는 것은 자명하지만, 문제를 그대로 구현하는 경우에는 시간 복잡도가 O(NK)가 되어 시간 초과가 난다. 큐를 사용하여 시간 복잡도를 O(N)까지 줄일 수 있다. 중요한 포인트는 다음과 같다. swap하는 경우 K 개의 요소를 모두 방문할 필요가 없다. 짝수 번 swap하면 element는 변하지 않는다는 점을 활용한다.

1. swap해야 하는 경우 몇 번째 인덱스까지 swap했는지 큐 저장한다.
2. 모든 element에 접근할 때마다, queue에 있는 최솟값이 자신의 수보다 작다면 popleft()를 해준다.
3. queue에 있는 요소의 갯수가 짝수인지 홀수인지를 확인하고, 홀수라면
   queue를 업데이트하여 swap한다.
4. swap을 할 때는 어느 index까지 swap했는지 저장한다.

import sys
from collections import deque

inp = sys.stdin.readline

n, k = map(int, inp().split())
lights = [i == "1" for i in inp().split()]
q = deque()
cnt = 0
for i in range(n + 1 - k):
    if q and q[0] < i:
        q.popleft()
    if (lights[i] and len(q) % 2 == 0) or (not lights[i] and len(q) % 2 == 1):
        q.append(i + k - 1)
        cnt += 1
for i in range(n + 1 - k, n):
    if q and q[0] < i:
        q.popleft()
    if (lights[i] and len(q) % 2 == 0) or (not lights[i] and len(q) % 2 == 1):
        print("Insomnia")
        break
else:
    print(cnt)