https://www.acmicpc.net/problem/17298
Problem
각 수에 대해 해당 수보다 오른쪽에 있으면서 더 큰 수 중 가장 왼쪽에 있는 수를 구하는 문제
오큰수가 없는 경우 -1을 출력
Solution
처음에는 단순 반복문을 이용했는데 시간초과가 났다.
이 문제는 스택을 이용해야 한다.
오큰수를 찾지 못한 수를 위해 결과 값을 저장하는 result 리스트를 크기만큼 -1로 초기화한다.
스택에는 인덱스를 넣어주고, 스택의 가장 위에 있는 값을 pop해서 다음 수와 비교한다.
이 비교는 스택에 값이 있을 때만 진행한다.
스택의 가장 위에 있는 인덱스(i)에 해당하는 값보다 오른쪽에 큰 수가 있으면 그 큰 수를 result[i]에 저장한다.
오큰수를 찾은 인덱스는 스택에서 pop해 제거해준다.
Python Code
DAilyHYUN.log