제일 작은놈 나와!!!!!!!!

문제

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를 공백으로 구분하여 순서대로 출력한다.

문제 아이디어

i-L+1부터 i 범위의 인덱스에서 최솟값을 찾는 것이 이 문제의 핵심이다. 그럼 우리는 2가지를 생각할 수 있다.
1. 매번 범위별로 C++에서는 max_element를 Python에서는 min을 사용하여 범위에서 최솟값을 찾는 것이다. 그러면 최대길이 N에서 범위 안에 들어있는 최솟값을 찾기 위해서는 N^2이 넘는것을 알 수 있다. 5백만의 제곱이면 말 안해도 알겠죠?
2. 자료구조를 사용하는 방법이다. 최솟값/최대값을 가장 잘 뽑아낼 수 있는 자료구조가 무엇이 있는가? 생각해보면 힙이 있다.
1번이 안된다는 것은 자다가 일어나도 알 수 있을테고, 우리는 2번을 통해서 문제를 해결해야만 한다.
풀이로 진행될 방법 총 2가지이다.
- Min Heap을 이용하는 방법
- deque 자료구조를 통해 Min Heap 처럼 이용하는 방법
- 우쨌든 Heap이 주를 이룬다고 보면 된다.

문제 풀이

우리가 생각해야 될 것은 매번 범위가 이동할 때마다 범위의 시작과 끝을 생각해주면 된다.
- 여기서 범위의 시작은 i-L+1일테고, 범위의 끝은 i가 될 것이다.
매번 i가 증가할 때마다 우리는 힙에 값을 넣어 그때 그때 루트에 있는 노드를 출력해주면 그것이 최소가 될 것이다. 그러나 생각해봐야 될 문제가 있다. 힙의 루트에 있는, 즉 최솟값이 범위 밖의 녀석이라면? 힙에 있는 값들은 인덱스 i와 같거나 작은 인덱스일 것이고, 범위 밖의 녀석이라는 것은 i-L+1 미만의 값이라는 것이다.
그러면, 우리는 최솟값을 뽑아내기 전에 루트를 확인해서, 루트가 현재 범위 안에 있는 녀석인지 확인해주면 된다.
이것을 힙과 deque으로 구현할 수 있는데 방법은 다음과 같다.
- 힙
  - 위에서 언급한 모든 내용들이 힙으로 구현하는 방법에 관한 내용이니 PASS
- 덱
  - 힙처럼 구현을 똑같이 한다고 생각하면 된다. 덱의 front에 최솟값이 저장된다고 생각하고, 매번 i를 증가하여 움직일 때마다 덱의 back으로 값을 넣어주면 된다. 여기서는 크게 2가지만 주의하면 된다.
    - 덱의 front에서 최솟값을 확인할 때, 범위 밖의 녀석이라면 pop을 해주고, 범위 안의 녀석이 나올때 까지 계속 pop 해주면 된다.
    - 덱의 back에 값을 넣어줄 때 넣는 값보다 큰 값이 존재하면, pop_back을 자기보다 같거나 작은 애들이 나올때 까지 해주면 된다.
코드를 봐보자!

Code(with Heap)- C++

Code(with Heap)- Python

Code(with Deque)- C++

Code(with Deque)- Python

문제의 문제

C++은 입출력이 아니면 통과하기가 조금 빡세다….
덱을 이용해서도 힙과 같은 역할을 할 수 있는 자료구조를 만들 수 있는 것은 오늘 처음 알았다,,