# 오큰수 = i보다 오른쪽에 있으면서 가장 큰수들 중 i와 제일 가까운(왼쪽)이 있는 수
# 오큰수가 없다면 -1
# 수열 개수만큼 반복
# stack에는 0번째 수가 들어있다. 0번째 수와 1번째 수 비교
# 0번과 1번 비교시 1이 크다면 result에 현재 인덱스에 큰 값 추가
# 크지 않다면 pop.
n = int(input())
num_ls = list(map(int, input().split()))
result = [-1 for _ in range(n)]
stack = [] # 각 인덱스를 저장
for i in range(n): # n만큼 반복
while stack and num_ls[i] > num_ls[stack[-1]]: # 현재 요소와 이전 요소들을 비교. 현재 요소가 이전 요소보다 크다면(=오큰수라면)
result[stack[-1]] = num_ls[i] # 현재 요소를 결과 배열의 이전 인덱스에 넣어줌
stack.pop() # 스택에서 제거 후 반복
stack.append(i) # 요소들의 인덱스를 stack에 추가. 0부터 시작함
print(*result)
https://www.acmicpc.net/problem/17298
'study > Algorithm' 카테고리의 다른 글
[백준] 파이썬 9375 : 패션왕 신해빈 (0) | 2024.04.04 |
---|---|
[백준] 파이썬 9935 : 문자열 폭발 (0) | 2024.04.04 |
[백준] 파이썬 2493번: 탑 (0) | 2024.04.04 |
[백준] 파이썬 2346 : 풍선 터뜨리기 (0) | 2024.04.04 |
[백준] 파이썬 1966번: 프린터 큐 (0) | 2024.04.04 |