백준 17298 : 오큰수
링크 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 가장 쉬운 방법은 for loop을 두 개 써서 O(n^2)의 시간 복잡도로 푸는 것입니다. 하지만 N이 최대 1,000,000까지 될 수 있기 때문에 당연히 시간 초과가 뜰 것입니다. 스택을 이용한다면 O(n)의 시간 복잡도로 풀 수 있습니다. 이렇게 모든 원소에 대해 원소 오른쪽/왼쪽에 어떤 조건을 만족하는 첫번째 원소를 구하라는 문제는 보통 단일 스택 (monotonic stack, 상황에 따라 ..