010 최솟값 찾기

첫번째 코드

 

윈도우 슬라이딩을 생각하여 그거에 맞게 코드를 작성했다!

now_list에 원소 하나를 추가하고 원소 하나를 제거하는 형식을 모든 단계에서 진행하고

now_list의  최소값을 내고 answer 리스트에 계속 업데이트 하는 형식으로 하는거지

 

import sys
input = sys.stdin.readline

n , l = map(int, input().split())
A = list(map(int, input().split()))

answer = [0] * n
now_list = []

for i in range(l):
    now_list.append(A[i])
    answer[i] = min(now_list)

for i in range(l, n):
    now_list.append(A[i])
    now_list.pop(0)
    answer[i] = min(now_list)

print(*answer)

 

시간초과...?

 

아아니이 그리고 pop()을 하면 맨 마지막 원소가 나가는데!! pop(0)을 사용하지 않아서 계속 1만 나와서 한참 찾았다...

---

두번째 코드

 

이거는 덱을 이해해야지 더 적은 용량으로 풀 수 있는 문제이다!

그래서 책을 참고해서 작성해보면 아래와 같다

비슷한데 덱을 사용한다는 것 정도로 생각하면 될 것 같다.

 

from collections import deque

n , l = map(int, input().split())
deq = deque()
A = list(map(int, input().split()))

for i in range(n):
    while deq and deq[-1][0] > A[i]:
        deq.pop()
    deq.append((A[i], i))
    
    if deq[0][1] <= i-l:
        deq.popleft()
    
    print(deq[0][0], end = ' ')

 

통과!

그치만 덱이 아직 익숙하지 않다!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Platinum/11003.%E2%80%85%EC%B5%9C%EC%86%9F%EA%B0%92%E2%80%85%EC%B0%BE%EA%B8%B0

programmers/백준/Platinum/11003. 최솟값 찾기 at main · ornni/programmers