17298:오큰수 [백준 문제풀이][Python]

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

난이도: 골드 4

스택을 이용하여 최댓값을 구하는 문제. 처음 보는 개념이라 이해하는데 꽤 애를 먹었다.

아이디어1

처음에는 단순하게 최댓값을 찾아서 계속 업데이트 해주는 방식을 생각해봤는데, 단순 계산으로도 O(n^2)이 넘어서 안된다. 입력 값이 10만이기 때문에 O(nlogn) 또는 O(n)으로 풀어야 된다.

아이디어2

다음은 스택을 사용한 풀이이다. 혼자 생각한건 아니고, 대충 찾아보면서 삽질 좀 했다.

스택은 선입후출(Last In Fisrt Out)의 방식을 가진 자료구조로, 선입선출 방식인 큐와 대비되는 방식이다. 

이를 이용해서 최댓값을 구할 수 있는데, 스택을 하나의 탑으로 보자면, 값이 들어올때마다 탑의 맨 윗부분부터 비교하면서 크면 아래로 보내준다. 이렇게 하면 마지막에 제일 아래 있는 값이 최댓값이 된다. 이 방식을 조금 응용하여, 오큰수라는 A보다 큰 값들 중 제일 오른쪽에 있는 값이니 스택을 업데이트 해주는 과정에서 어떤 한 값이 아래로 내려간다는 것은 그 값이 더 크다는 것을 의미하니 pop을 해주며 업데이트 해주면 된다.

스택 안에 아무것도 없으니 3을 그대로 넣는다.

5를 넣고, 3이 5보다 작으니 pop해주면서 NGE리스트를 업데이트 해준다.

2는 5보다 작으니 그대로 넣는다.

2,5는 7보다 크니 pop해주면서 업데이트 해준다.

정답 코드

import sys
input = sys.stdin.readline
n=int(input())
l=list(map(int,input().split()))
stack = []
c = [-1]*n
for i in range(n):
    while len(stack)!=0 and l[i]>l[stack[-1]]:
        c[stack.pop()]=l[i]
    stack.append(i)
print(*c)