[백준] 11003번 최솟값 찾기 (Python)

백준 11003 최솟값 찾기

첫 오답

슬라이딩 윈도우를 활용하여 탐색해야 한다. 처음에는 힙(우선순위큐)을 이용하여 문제를 풀었다. 힙을 활용하였고, 힙의 root node가 삭제해야 할 값과 다르다면 defaultdict()를 활용하여 삭제되어야 할 숫자와 갯수를 저장하여 제거했다. 하지만 힙을 활용하기 때문에, 원소를 추가하거나 제거할 때 힙을 재구성하는 데 O(logn) 시간이 걸린다. 결국 TLE가 났고, O(n) 시간 복잡도로 해결할 수 있는지 고민했다.

나의 답

우선순위 큐를 포기하고 deque를 사용하기로 했다. 몇 가지 중요한 아이디어가 있다.

1. 현재 추가된 값보다 큰 값은 절대로 최솟값이 될 수 없다 즉, deque에서 삭제해도 된다.
2. 삭제되는 값이 deque에서의 최솟값과 같다면 삭제한다. deque에서 최솟값 보다 크다면 이미 삭제되었을 것이다.
3. 추가되는 부분인 오른쪽 포인터와 삭제되는 부분인 왼쪽 포인터를 활용한다.

모든 입력 값은 deque의 오른쪽으로 들어가고, 자신보다 큰 값은 모두 pop한 이후에 append 한다. 제거해야 하는 값과 deque의 왼쪽 값을 비교하고 같다면 popleft한다.

구글링하다가 본 가장 깔끔한 코드

from collections import deque
n, l = map(int, input().split())
arr = [*map(int, input().split())]
m = deque()
for i in range(n):
    tmp = arr[i]
    while m and m[-1] > tmp: m.pop()
    m.append(tmp)
    if i >= l and m[0] == arr[i - l]: m.popleft()
    print(m[0], end=' ')

내 코드

나는 lp가 0일 때와 rp만 고려할 때 두 가지 경우로 나누었다.

import sys
from collections import deque

input = sys.stdin.readline
n , l = map(int, input().split())
seq = list(map(int, input().split()))
slide = []
dq = deque()

rp = 0
tl = l
while tl > 0:
    tl -= 1
    while dq and dq[-1] > seq[rp]:
        dq.pop()
    dq.append(seq[rp])    
    print(dq[0], end = ' ')
    rp += 1
lp = 0

while rp < n:
    # print(dq)
    if seq[lp] == dq[0]:
        dq.popleft()
    while dq and dq[-1] > seq[rp]:
        dq.pop()
    dq.append(seq[rp])
    print(dq[0], end = ' ')
    rp += 1
    lp += 1