PS
백준 17299. 오등큰수
tose33
2023. 1. 21. 14:01
https://www.acmicpc.net/problem/17299
17299번: 오등큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
스택인걸 알면 쉬운데 알기까지가 어려운 문제.
스택에 {숫자, F(숫자)} 를 저장한다.
뒤에서부터 앞으로 탐색하면서 스택의 top의 F(A)가 현재 F(Ai) 작거나 같을때까지 모두 pop 시킨다.
그럼 결론적으로 스택의 top에 현재 F(Ai) 보다 F(A)가 크고, 스택 자료구조 특성상 나보다 오른쪽에 있으면서 최초로 등장한것이 남게된다.