백준 #3015 - 오아시스 재결합

모노톤 스택으로 푸는게 맞다.
다만, 문제 풀이 중 고려한 부분에 대해 나열한다.

1. n<=500,000인 경우 O(n)을 염두해 두어야 함(O(n^2)는 무조건 시간초과)

2. 왼쪽에서 오른쪽으로 기준을 바꿀 때 스택을 어떤 순서로 정렬할 지 결정

   해당 문제에서는 두 끝 사람 사이에 키가 큰 사람이 있으면 안되므로 내림차순 정렬이 옳다.

3. 스택을 pop으로 정렬하는 과정에서 ans을 반영

4. 같은 키에 대해서는 예외가 많이 발생, 따라서 pair<>를 사용하여 같은 키에 대해서는 한 노드에 개수 정보까지 저장해서 정렬

이 문제를 스택으로 풀어야겠다고 생각하는 것이 첫째, 같은 키에 대해서 개수 정보를 한 노드에 저장하는 것이 둘째로 어려운 포인트였다.

p.s. 나름 도움없이 혼자서 풀어서 만족함

문제

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