코딩테스트 대비/단계별 코딩 테스트 준비(27일 과정)
[스택/Python] 17298번: 오큰수 - 효과는 굉장했다!
bluetag_boy
2022. 2. 11. 21:20
반응형
17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
알고리즘 분류
- 자료 구조
- 스택
SOLUTION
import sys
A = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
stack = []
ans = [-1 for _ in range(A)]
for i in range(A):
# 스택이 비지 않고 stack의 가장 마지막으로 append 된 인덱스인 num[idx]가 num[i] 보다 작다면
while stack and num[stack[-1]] < num[i]:
# 오큰수 stack을 pop해주면서 해당 idx에 자신보다 가장 큰 왼쪽에 있는 수를 넣어줌
ans[stack.pop()] = num[i]
stack.append(i)
print(*ans)