[백준] 파이썬 17298번: 오큰수

 

 

# 오큰수 = 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