첫번째 코드
윈도우 슬라이딩을 생각하여 그거에 맞게 코드를 작성했다!
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 = ' ')
통과!
그치만 덱이 아직 익숙하지 않다!
링크
'코딩 테스트 > do it! 알고리즘 코딩테스트' 카테고리의 다른 글
011 스택 수열 (0) | 2024.04.18 |
---|---|
012 오큰수 (0) | 2024.04.18 |
009 DNA 비밀번호 (2) | 2024.04.15 |
008 좋아 (2) | 2024.04.11 |
007 주몽 (0) | 2024.04.11 |