bong-u/til

🏠 home 🐈 repository

백준 - 11003 : 최솟값 찾기 (P5)

수정일 : 2024-11-15

 1from collections import deque
 2N, L = map(int, input().split())
 3A = list(map(int, input().split()))
 4
 5Q = deque([(A[0], 0)])
 6result = [A[0]]
 7
 8for i in range(1, N):
 9if Q[0][1] == i-L:
10Q.popleft()
11while Q and Q[-1][0] >= A[i]:
12Q.pop()
13Q.append((A[i], i))
14result.append(Q[0][0])
15
16print(*result)

문제

  • N개의 수 A1, A2, …, AN 과 L이 주어진다.
  • Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오.
  • TC
    • input

      12 3
      1 5 2 3 6 2 3 7 3 5 2 6

    • output

      1 1 1 2 2 2 2 2 3 3 2 2

시도 1

  • deque을 통해서 슬라이딩 윈도우 방식으로 접근하였다.
    • deque의 구조 [수1, 수2, …]
  • 최솟값을 구할 때 min(queue) 와 같이 구해보았다.
  • L의 최댓값이 5,000,000 이기 때문에 시간이 초과될 수 밖에 없다.

해결 방법

  • deque을 사용하는 방식은 시도 1과 같다.

  • 조건

    • 최솟값을 바로바로 얻어내기 위해 deque이 정렬된 상태를 유지하도록 한다.
    • 정렬된 상태를 유지하는 경우 index가 뒤죽박죽 되기 때문에, index도 deque에 저장한다.
      • deque의 구조 [(수1, index1), (수2, index2), …]
  • 구현
    • deque의 맨 왼쪽에 있는 수의 index를 보고 빼야하는 경우 popleft를 한다
    • 필요 없는 수(새로 들어오는 수보다 큰 수) 를 지운다
      • 예 : deque(1, 5) 새로운 원소(2) 필요없는 원소 = 5
    • 새로운 수를 deque의 오른쪽에 넣는다
    • deque의 왼쪽에 있는 값을 결과리스트에 추가한다.
    • 위 작업을 반복한다.