[BOJ] 11003번: 최소값 찾기

https://www.acmicpc.net/problem/11003

원소가 크기 오름차순으로 들어가있는 deque를 이용해 문제를 해결합니다. deque에는 값, 인덱스 pair를 넣습니다. 문제의 예시 1 5 2 3 6 2 3 7 3 5 2 6 으로 설명을 해보겠습니다.

우선 1에 대해 deque의 back에 (1, 0)을 삽입하고 front의 값인 1을 출력합니다.   (1,0)

5에 대해 deque의 back에 (5, 1)을 삽입하고 front의 값인 1을 출력합니다.   (1,0) (5,1)

2에 대해 deque의 back에 (5, 1)을 꺼내고(2가 5보다 작으므로) (2, 2)를 삽입하고 front의 값인 1을 출력합니다. (1,0) (2,2)

3에 대해 deque의 back에 (3, 3)을 삽입하고 front에서 (1, 0)을 꺼내고(L = 3이므로) front의 값인 2를 출력합니다.

.

.

.

이와 같이 하면 각 원소는 최대 1번 deque에 들어가고 1번 deque에서 제거되므로 O(N)임을 알 수 있습니다.

priority queue나 segment tree를 이용해서 O(NlgN)에 풀 수도 있으나, N이 굉장히 커서 잘 짜지 않으면 O(NlgN)에도 시간 초과가 발생할 것입니다.

https://github.com/blisstoner/BOJ/blob/master/11003.cpp