최솟값 찾기 백준 11003번 덱

https://www.acmicpc.net/problem/11003

문제 N개의 수 A1, A2, …, AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

백준이 문제가 많은거는 좋은데…. 테스트케이스가 너무 몇 개 주지를 않아서 아쉽습니다.

문제의 분류는 덱인데 슬라이딩해가면서 최솟값을 구한다고 생각을 했습니다. m의 크기는 슬라이딩의 크기가 됩니다. 그러면 해당 슬라이딩에 들어가는 숫자를 덱으로 관리를 하면 될듯합니다.

n,m = map(int,input().split())
num_list = list(map(int,input().split()))
from collections import deque
min_list = deque([])
ans = []
min_num = num_list[0]
for i in range(n):
    if len(min_list)!=m:
        min_list.append(num_list[i])
        min_num = min(min_num,num_list[i])
    else:
        temp = min_list.popleft()
        min_list.append(num_list[i])
        if min_num==temp:
            min_num=min(min_list)
        elif min_num>num_list[i]:
            min_num=num_list[i]
    ans.append(min_num)
print(*ans, sep = ' ')

그냥 좀 몇 가지 무식하게 생각을 하면서 나갔습니다. 먼저 처음 리스트에는 아무것도 들어있지 않으니 L크기만큼 받아 나가면서 제일 작은 값을 기록하고 ans에 추가를 합니다.

이제 슬라이싱을 하면서 값이 빠지고 들어오고 할것인데 값이 빠졌는데 그게 지금의 최소값이라면 새로 min값을 계산하고 들어오는 값이 작은 값보다 더 작다면 갱신하는 식이었는데…. 시간초과가 났습니다.

새로 min값을 갱신하는 부분을 어떻게 O(1)으로 처리하는 방법을 찾아야 할거 같았는데 이부분에서 우선순위 heap를 사용하면 되지 않을까 했으나

n,m = map(int,input().split())
num_list = list(map(int,input().split()))

from collections import deque
import heapq
min_list = deque([])
ans = []
for i in range(n):
    if len(min_list)!=m:
        min_list.append(num_list[i])
        min_num = min(min_num,num_list[i])
    else:
        temp = min_list.popleft()
        min_list.append(num_list[i])
        if min_num==temp:
            check = list(min_list)
            heapq.heapify(check)
            min_num=check[0]
        elif min_num>num_list[i]:
            min_num=num_list[i]
    ans.append(min_num)
print(*ans, sep = ' ')

코드만 더 괴랄해지고 정답도 아니네요

n,m = map(int,input().split())
num_list = list(map(int,input().split()))
from collections import deque
dq = deque([])
for i in range(n):
    num = num_list[i]
    while dq and (dq[-1][1] >= num):
        dq.pop()
        
    dq.append([i,num])
    
    if dq[0][0] <= (i-m):
        dq.popleft()
        
    print(dq[0][1], end = ' ')

덱으로 깔끔하게 풀 수 있네요 천천히 봅시다. 덱은 먼저 (인덱스, 입력 숫자)의 형태로 데이터를 저장합니다.

첫번째 테스트 케이스인 <1 5 2 3 6 2 3 7 3 5 2 6> 기준으로 보겠습니다.

먼저 덱은 [0,1]이 들어가게 되고 덱에서 가장 위에 있는 1을 출력합니다.

그 다음 5가 들어가게 되는데 while조건에 들지 않았으니 5도 그대로 넣어 줍니다.

덱에는 [0,1] [1,5] 두가지가 들어가게 됩니다. 여전히 1이 제일 위에 올라와있으니 1을 출력합니다.

2가 들어오게 되는ㄷ while조건문에 걸리게 됩니다. 덱에서 뒤에서 제일 위에 올라온거는 5인데 이는 2보다 크기 때문입니다. pop으로 빠져 나가고 추가를 합니다. 덱에는 [0,1], [2,2] 여전히 제일 위에 있는 1을 출력합니다.

그 다음으로 3을 넣게 되는데 문제는 슬라이딩 크기가 제한이 되었습니다. 제일 위에 있는 인덱스는 0이었는데 조건에 따라 (4-3)보다 작은 값이 되었으니 빠지게 됩니다.

계속해서 덱에서는 두번째로 작은수만 갱신되서 남아 있기 때문에 최솟값을 낼 수 있습니다.