골드 1 최솟값 찾기

문제: 골드 1 최솟값 찾기

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

 

풀이코드

import sys
from collections import deque

input = sys.stdin.readline
# 덱에 (값, 인덱스)를 넣고 항상 최솟값이 맨 앞에 오게끔 
# + 인덱스 범위에 없는 거면 삭제
N, L = map(int, input().split())
lst = list(map(int, input().split()))
d = deque()
out = []

for i, x in enumerate(lst): 
    # 새로 들어오는 값이 d에 있는 값보다 작다면 제거
    while d and d[-1][0] > x: 
        d.pop()
    d.append((x, i))
    
    # 윈도우 밖 인덱스 제거
    while d and d[0][1] < i-L+1: 
        d.popleft()
    out.append(d[0][0])
print(*out)

---

느낀 점

일단 덱의 특성을 다시 한 번 살펴보자. 

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조로 두 개의 포인터를 사용한다. 

from collections import deque

dq = deque([1,2,3,4])

dq.appendleft(-10)        # 왼쪽에 데이터 삽입
dq.append(10)             # 오른쪽에 데이터 삽입

print(dq.pop())           # 오른쪽에서 데이터 제거
print(dq.popleft())       # 왼쪽에서 데이터 제거

 

흔히 쓰는 append와 pop에다가 left만 붙이면 맨 앞에서 삭제할 수 있는 포인터를 활용할 수 있다. 

 

맨 처음에 본 문제를 풀 때는 다음과 같이 접근했다. 

import sys
input = sys.stdin.readline

N, L = map(int, input().split())
lst = list(map(int, input().split()))
ans = []
for i in range(N): 
    start = max(i-L+1, 0)
    l = lst[start:i+1]
    ans.append(min(l))
print(*ans)

 

이렇게 풀었더니 당연하게도 시간초과가 났다. for문으로 돌면서 리스트를 만들고 min을 찾으면서 당연하게 시간초과가 난 것이다. 

 

어떻게 할 수 있을까? 뭔가 인덱스를 윈도우처럼 활용해서 윈도우에 해당하지 않는 인덱스라면 삭제할 수 있을 것 같았다. 

덱을 활용하려면 앞에서 넣거나 빼고 뒤에서 넣거나 빼야 할 것 같은데... 

GPT에게 정답을 절대 절대 알려주지 말고 힌트만 달라고 했다... ㅎㅎㅎ

 

일단 가장 먼저 deque을 만들었다. 그리고 정답이 들어갈 out 리스트를 만들었다. 

덱에는 값과 인덱스가 튜플로 들어가며 항상 최솟값이 맨 앞에 오게끔 한다. 즉, 윈도우 내에 있는 최소값을 min으로 찾을 필요 없이 popleft를 하면 바로 최솟값을 찾을 수 있게 해둬야 하며 덱에는 항상 인덱스 범위 안에 있는, 윈도우 안에 있는 수들만 들어가있어야 한다. 

 

enumerate로 for문을 돌린 다음 덱이 존재하고 덱의 가장 오른쪽에 있는 값보다 새로 들어오는 값이 작다면 제거한다. 

for i, x in enumerate(lst): 
    # 새로 들어오는 값이 d에 있는 값보다 작다면 제거
    while d and d[-1][0] > x: 
        d.pop()

왜 이렇게 해야 하나? 

일단 가장 작은 값이 맨 앞으로 오게끔하면 만약 윈도우가 3일 때...

[(1, 0), (2, 1), (3, 2)] 에서 2가 다음으로 들어오면 [(1,0), (2, 1), (2, 3)] 이렇게 된다. 그러면 아무리 다음 숫자가 들어오더라도 해당 윈도우에서의 최솟값은 3이 될 수 없다. 때문에 제거해주는 것이다. 

좀 더 깔끔하게 정리하자면...  새로 들어온 값 x가 더 작으면 덱 뒤의 큰 값들은 x가 있는 동안 절대 최솟값이 될 수 없으니 제거하게 되는 것이다. 

 

그 후 새로 들어오는 값을 넣어준다. 

그리고 [i-L+1, i]인 윈도우 밖 인덱스를 제거해주어야 한다. 

    while d and d[0][1] < i-L+1: 
        d.popleft()

이때는 맨 왼쪽에 있는 인덱스가 문제에서 제시한 i-L+1 보다 작다면 윈도우 범위 밖으로 나간 것이기 때문에 덱의 가장 앞쪽 원소의 인덱스와 비교해서 popleft를 해준다. 

 

그런데 여기서 궁금한 점이 생겼다. 

왜 덱의 가장 앞쪽 원소의 인덱스와 비교하는 걸까? 덱은 무조건 지금 값을 기준으로 정렬될텐데..

조금 생각해보면 나는 중간 삽입을 해주지 않고 계속해서 앞 뒤로 추가를 해주고 있다. 그렇다면 덱 내부에서 인덱스 순서는 자연스럽게 맨 앞이 가장 작은 인덱스를 가지고 있을 것이다. 

 

이건 나중에 한 번 더 풀어봐야겠다!