알고리즘/백준
[백준] 17298 오큰수 (Python)
문제 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 풀이 해당 문제의 입력이 백만 개가 들어올 수 있으므로 O(N)만큼의 시간복잡도로 해결해야 하는 문제. 단순히 각 원소를 접근할 때 마다 오른쪽의 원소와 비교하며 오큰수를 발견 시 이를 출력하게 되면 O(N^2)로 문제 해결이 되지 않는다. 따라서 문제 해결을 위해 다른 방법을 찾아야 했다. 필자는 다음과 같이 생각했다. 1) 오른쪽에 작은 수가 들어오게 되면 해당 수는 쓸모가 없는 수가 되는 것일까 2) 오른쪽에 큰 수가 들어오게 되면 이전 수에도 영향을 미치지..
