1. 아이디어
정방향으로 순회하면서 어떻게하면 스택을 이용하여 문제를 해결할 수 있을까하며 30분동안 고민했지만 아이디어가 떠오르지 않았다. 그래서 역방향으로 순회해서 문제 해결을 시도했는데 됐다.
배열의 마지막 원소를 stack에 삽입하고 그 다음 원소부터 역방향으로 탐색을 시작한다. 현재 인덱스가 가리키는 배열의 원소와 stack에 저장된 마지막 원소를 비교한다. stack의 마지막 원소가 현재 인덱스가 가리키는 배열의 원소보다 클 때까지 pop연산을 한다. 그리고 그 원소(stack의 마지막 원소)를 다른 변수에 기록한다. 남아있는 stack이 없다면, -1를 기록한다. 이후, 현재 인덱스가 가리키는 배열의 원소 값을 stack에 삽입한다.
백준 예제 입력 1을 이용하여 설명하면, 입력으로 주어진 배열(arr),[3, 5, 2, 7]과 오큰수를 담는 배열, answer의 모든 원소가 -1로 초기화 되어있다.
우선, arr의 마지막 원소를 stack에 삽입하자. 따라서 stack = [7]이다. 그리고 arr의 마지막에서 2번째 원소부터 1번째 원소까지 역방향으로 탐색을 한다. arr[2]는 2이므로 stack의 마지막 원소인 7보다 작다. 따라서 answer[2]=7이다. 그리고 2를 stack에 삽입한다.
arr[1]은 5이다. 5는 stack의 마지막 원소인 2보다 크다. 따라서 stack에서 pop한다. pop연산 이후, stack의 마지막 원소는 7이다. 7은 5보다 크므로 answer[1]=7이다. 그리고 5를 stack에 삽입한다.
arr[0]은 3이다. 3은 stack의 마지막 원소인 5보다 작다. 따라서 answer[0]=5이다.
따라서 정답은 [5,7,7,-1]이다.
2. 코드
import sys
n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().rsplit()))
def solve():
if n == 1: return [-1]
answer = [-1 for _ in range(n)]
stack = []
stack.append(arr[-1])
for i in range(n-2, -1, -1):
while stack and arr[i] >= stack[-1]: stack.pop()
answer[i] = -1 if not stack else stack[-1]
stack.append(arr[i])
return answer
answer = solve()
for a in answer: print(a, end=' ')