반응형
11003
-
BOJ) 최솟값 찾기 (11003 번)알고리즘/백준 2021. 1. 29. 16:36
최솟값 찾기 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 슬라이딩 윈도우를 이용하는 문제로, N개의 수와 윈도의 크기 L이 주어진다. D(i) = A(i-L+1) ~A(i) 중의 최솟값이라고 할 때, D에 저장되는 값을 출력하는 문제다. 즉, 자신의 위치에서 L칸 앞선 칸들 중 최솟값을 찾는 문제다. 처음에는 우선순위 큐로 시도하다가, 시간초과가 떴다. 아무래도 최악의 경우에는 O(N)이 추가돼서 그런 것 같다. (while을 통해 인덱스 범위를 검증하는 과정) 그래서 Deq..