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

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

17298번: 오큰수

 

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

 

문제 이해는 쉬웠는데, 여러 접근을 하려다가 시간이 굉장히 오래걸린 문제이다.

 

해설지를 보았는데, 세상에,, 사람들은 짱이다.

index를 stack에 넣어서 코드풀이를 할 생각은 못했었다. 더 넓은 관점을 배울 수 있었다.

대단하다.

 

코드 해석

먼저 입력받은 값을, list_num이라는 list에 넣어주고, stack은 아무것도 없게 초기화해준다.

stack이 비어있지 않을때까지, 그리고 list_num[stack[-1]] < list_num[i] 클 때에, 해당 stack에 들어가 있는 index를 빼주고, 해당 index에 큰 값을 넣어준다. 그것이 오큰수이다.

 

그리고 거기서 큰 값이 없어서 stack.pop()을 해주지 못한 index들은 큰 값이 없는 것이니, 마지막에 모두 pop을 해주면서 -1로 해준다.

 

정답 코드

그래도 그대로 따라가지는 않고, 내 편한대로 변형해서 진행했다.

import sys
input = sys.stdin.readline

num = int(input())

list_num = list(map(int, input().split()))

stack = []

for i in range(0, num):
    while((len(stack)!=0) and (list_num[stack[-1]] < list_num[i])):
        list_num[stack.pop()] = list_num[i]
    stack.append(i)

while(stack):
    list_num[stack.pop()] = -1

print(" ".join(map(str, list_num)))