[solved.ac 골드1] 11003_최솟값 찾기 (파이썬, 슬라이딩 윈도우)

https://github.com/mangbaam/CodingTest

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

 

문제

입력

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

예제

---

나의 풀이

이 문제는 L 크기의 범위에서 최소 값을 찾아나가는 문제이다. 문제 자체가 슬라이딩 윈도우를 사용하라고 하는 것 같다.

주의할 점은 윈도우의 크기가 클수록 그 안에서 최소 값을 찾는데 시간이 오래걸리기 때문에 선형 탐색보다는 다른 방식으로 찾아야 한다는 점이다.

가장 작은 값을 가지고 있다가 새로운 값이 들어올 때마다 가장 작은 값을 갱신하는 방식도 생각해보았지만 슬라이딩 윈도우가 이동하면서 가장 작은 값이 빠져나가게 되면 다시 윈도우 안에서 가장 작은 값을 탐색해야 한다.

처음에는 Heap 을 사용해서 찾으려고 했는데 그러려면 윈도우 안에 있는 숫자들의 리스트를 가지고 있어야 했고, 윈도우가 이동하면서 숫자가 빠져 나가면 또 그거대로 시간이 많이 소요된다.

 

해결 방법은 정렬이다. 그런데 매번 정렬하는 것이 아니라 새로운 값이 들어오면 그 값보다 작은 값들은 모두 윈도우에서 제거한다. (슬라이딩 윈도우를 구현하기에 가장 적합한 자료구조가 Deque 이라서 Deque 을 사용했다. 이하 "큐" 라고 부르겠음)

큐에 저장할 값은 숫자 뿐만 아니라 윈도우의 크기를 유지하기 위해 인덱스도 함께 저장한다

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

 

위 숫자들이 입력으로 주어지고, 윈도우 크기가 3일 때

 

처음에는 (0, 1) 이 들어온다 (인덱스, 값)

 

그 다음에는 (1, 5) 가 들어올 차례인데 이전 값이 1이므로 오름차순이 유지되기 때문에 큐에 넣는다.

현재 큐에는 (0, 1), (1, 5) 가 들어있다.

 

그 다음에는 (2, 2) 가 들어올 차례인데 이전 값이 5라서 오름차순이 유지되지 않는다. (1, 5)를 빼내고 큐에 (2, 2)를 넣는다.

현재 큐에는 (0, 1), (2, 2) 가 들어있다.

 

(3, 3)이 들어올 차례이다. 오름차순이 유지되기 때문에 넣을 수 있다.

현재 큐에는 (0, 1), (2, 2), (3, 3) 이 들어온다.

그런데 인덱스를 보면 0번 인덱스부터 3번 인덱스가지 총 4개의 값이 들어있는 셈이다. 윈도우 크기를 유지하기 위해서 맨 앞의 값을 하나 빼낸다.

그러면 현재 큐에는 (2, 2), (3, 3) 이 들어있다.

 

(4, 6)이 들어올 차례다. 오름차순이 유지되기 때문에 넣을 수 있다.

현재 큐에는 (2, 2), (3, 3), (4, 6) 이 들어있다. 2, 3, 4 인덱스가 들어있는 셈이니까 윈도우 크기를 넘지도 않았다.

 

(5, 2)가 들어올 차례다. 오름차순이 유지되지 않기 때문에 더 작은 값을 만날 때까지 큐에서 제거하고 넣는다

(2, 2), (5, 2) 가 된다. 그런데 인덱스를 보면 2, 3, 4, 5 인덱스가 들어있는 셈이니까 윈도우 크기를 넘었기 때문에 맨 앞에서 하나를 제거한다.

결과적으로 현재 큐에는 (5, 2)가 들어있다.

 

(6, 3)이 들어올 차례다. 오름차순이 유지되기 때문에 그대로 집어 넣는다.

현재 큐에는 (5, 2), (6, 3) 이 들어있다.

 

(7, 7) 이 들어온다. 넣을 수 있기 때문에 넣는다.

현재 큐에는 (5, 2), (6, 3), (7, 7) 이 들어있다.

 

(8, 3) 이 들어온다. 3보다 더 큰 값들은 제거하므로 (7, 7)이 제거된다.

(5, 2), (6, 3), (8, 3) 이 들어있는데 윈도우 크기를 넘었으므로 맨 앞 요소를 뺀다

현재 큐에는 (6, 3), (8, 3) 이 들어있다.

 

(9, 5) 가 들어온다. 집어 넣으면 (6, 3), (8, 3), (9, 5) 가 되고, 윈도우 크기를 넘었으므로 맨 앞 요소를 뺀다.

현재 큐에는 (8, 3), (9, 5) 가 들어있다.

 

(10, 2) 가 들어온다. 큐에 들어있는 요소가 모두 제거된다.

현재 큐에는 (10, 2) 가 들어있다.

 

(11, 6) 이 들어온다.

현재 큐에는 (10, 2), (11, 6) 이 들어있다.

 

탐색이 종료된다.

 

이처럼 인덱스와 값을 함께 넣으면서 오름차순을 유지하면 O(N) 복잡도로 최솟값을 찾으면서 진행할 수 있다.

큐의 맨 앞 요소에 최솟값이 들어있는 것이다. 굵게 표시해놓은 것이 현재 윈도우에서 가장 작은 숫자인 것이다.

 

전체 코드

from collections import deque

N, L = map(int, input().split())
li = list(map(int, input().split()))
q = deque()

for i in range(N):
    while q and q[-1][1] > li[i]:
        q.pop()
    q.append((i, li[i])) # 인덱스, 값
    if i - q[0][0] >= L:
        q.popleft()
    print(q[0][1], end=' ')

 

채점 결과