📩 출처
문제
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
출력
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
👉 생각
- 일일히 찾으면 시간초과가 발생할 것이라고 생각해서 스택을 적용해보기로 했고 스택의 기본값은 0으로 lst 리스트의 첫번째 인덱스를 넣어주었다.
- 인덱스를 넣어준 것은 answer의 기본 값이 다 -1이 이고 이를 인덱스를 통해 바꿔줄 것이기 때문이다!
- 스택에 top을 인덱스로 하는 값이 for문을 통해 들어오는 값보다 작다면 오큰수를 의미하기 때문에 top을 pop해준 값을 answer의 인덱스로 취하고 lst[i]로 값을 준다. while을 통해 lst[i]를 오큰수로 만족하는 애들이 더 있을 수 있기 때문에 계속 pop해준다!
n = int(input())
lst = list(map(int, input().split()))
answer = [-1 for _ in range(n)]
stack = [0]
for i in range(1, n):
while stack and lst[stack[-1]] < lst[i]:
answer[stack.pop()] = lst[i]
stack.append(i)
print(*answer)