알고리즘 - Python / 백준 - 17298번 : 오큰수

17298번: 오큰수 (acmicpc.net)

17298번: 오큰수

 

---

풀이

• 수열이 주어지고 , 그 숫자보다 오른쪽에서 큰 숫자들 중 가장 먼저 나오는 수가 오큰수 이다.
• 주어진 수열에 대하여 오큰수(An)을 찾으면 되는 문제다.
• 스택을 통해서 구현할 수 있고 , 다음과 같은 방식으로 해결하면 된다.
• 1. 스택의 TOP과 비교해 다음 수가 크다면 , POP 하고 그다음수를 오큰수로 정함
• 2. 스택의 TOP과 비교해 다음 수가 작다면 , 스택 위에 추가함
• 1번의 경우 스택이 빌 때까지 진행하고 , 2번의 경우는 더 진행할 필요가 없으므로 break 하여 while 문을 빠져나온다.
• 위의 1번 ~ 2번 과정을 주어진 모든 수열에 대해 반복하면 정답이 나온다.

 

import sys
n = int(sys.stdin.readline())
s = list(map(int , sys.stdin.readline().split(" ")))
stack = []
stack.append([s[0],0])
ans = [-1 for i in range(n)]
for i in range(1,n):
    while stack:
        if stack[-1][0] < s[i]:
            pp = stack.pop(-1)
            ans[pp[1]] = s[i]
        else:
            break
    stack.append([s[i],i])

for i in range(0,len(ans)-1):
    print(ans[i],end=" ")
print(ans[len(ans)-1])

---