#110 백준 파이썬 [17298] 오큰수 - 스택

https://www.acmicpc.net/problem/17298

 

 

#Solution

이 문제는 스택으로 풀어야한다. 특이한 점은 index를 스택에 넣어주어야한다는 점!! 다음과 같은 논리를 따라서 결과값을 출력한다.

 

0) result / stack / num_list 세 개의 리스트를 만들어준다.

1) n번 루프를 돌린다. O(n) for문은 index인 i를 기준으로 돌아간다.

2-1) 스택이 비어있으면 i를 스택에 넣어준다.

2-2) 스택의 top이 가르키는 num_list[top] 이 num_list[i]보다 크거나 같으면 i를 스택에 넣어준다.

2-3) 스택의 top이 가르키는 num_list[top] 이 num_list[i]보다 작으면 스택을 pop해주고 result[pop값]에 num_list[i]를 넣어준다.

2-3-1) 스택이 비거나 조건을 만족하지 못할 때 까지 반복한다.

2-3-2)스택에 i를 추가해준다.

numbers = int(input())
num_list = list(map(int, input().split()))
stack = []
result = [-1 for _ in range(numbers)]

for i in range(len(num_list)):
    try:
        while num_list[stack[-1]] < num_list[i]:
            result[stack.pop()] = num_list[i]
    except:
        pass
        
    stack.append(i)
        
for i in range(numbers):
    print(result[i], end = ' ')