최소값 찾기

"be creative"

[문제]

N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최소값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

[입력]

• 첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)
• 둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

[출력]

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

[실행 예]

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

1 1 1 2 2 3 4 4 3 3 2 2

---

10 4 3 5 1 3 2 4 7 5 3 2

3 3 1 1 1 1 2 2 3 2

---

해결 방법 heapq 라이브러리를 이용해 i 값 별로 최소 heap의 루트 노드가 인덱스 범위를 벗어나 있으면 노드를 pop 시킨 후 범위에 들어오는 노드를 삽입하고, 루트노드(최솟값)를 최솟값 리스트에 삽입하게 된다.

특히, 구간에서의 최솟값을 알고 싶은 것이기 때문에 min_heap의 루트 노드 값이 구간 내에 들어오도록 영속성 을 유지해주고, 루트 노드만을 꺼내오면 그것이 그 구간의 최솟값이 되는 것이다.

여기서 중요한 것은 min_heap에 특정 구간의 모든 값이 들어간다던가 하는 클래식한 방법이 아닌, 다소 변칙적 인 방법을 이용해 문제를 해결한다는 것이다.

또, heap에 숫자만을 삽입하게 되면 index를 이용해 비교하는 것이 불가능하다. 그래서 node 클래스를 이용해 key와 index를 갖게 하고, lt 메서드를 이용해 정렬 기준을 key로 지정해주었다.

또, 이전 문제들과 마찬가지로 성능을 위해 input을 sys 라이브러리의 readline 함수로 재정의해주었다.

이 알고리즘은 아래와 같은 과정으로 동작한다.

i	i-L+1 (>=0)	min_heap	min_list
0	0	[1]	[1]
1	0	[1,5]	[1,1]
2	0	[1,2,5]	[1,1,1]
3	1	[2,3,5]	[1,1,1,2]
4	2	[2,3,5,6]	[1,1,1,2,2]
5	3	[3,4,5,6]	[1,1,1,2,2,3]
6	4	[4,5,5,6]	[1,1,1,2,2,3,4]
7	5	[4,5,5,6,7]	[1,1,1,2,2,3,4,4]
8	6	[3,5,5,6,7]	[1,1,1,2,2,3,4,4,3]
9	7	[3,5,5,5,6,7]	[1,1,1,2,2,3,4,4,3,3]
10	8	[2,3,3,5,5,5,6,7]	[1,1,1,2,2,3,4,4,3,3,2]
11	9	[2,3,3,5,5,5,6,6,7]	[1,1,1,2,2,3,4,4,3,3,2,2]

그런데 백준 사이트에서 제출하니 시간 초과 문제를 직면했다. 조교님께 질문해본 결과 "PyPy3"를 이용해보라는 말씀을 들었고, 검색해보니 PyPy3는 JIT 컴파일러를 이용해 기존의 파이썬 대비 훨씬 빠른 퍼포먼스를 자랑하는 언어였다. 그래서 단순히 PyPy3로 언어를 바꿔서 제출하니 성능 기준을 통과할 수 있었다.