[Baekjoon]백준 17298 오큰수(골드 4) - Python

문제설명

문제를 살펴보면 특정 index에서 오른쪽에 존재하는 수 중에서 큰 값을 찾으면 된다

대신 그냥 큰 값이 아니라 가장 왼쪽에 위치한 큰 값이다 i의 오큰수를 찾는다고 가정하면 i+1, i+2...를 거듭하면서

A[i] 값보다 더 큰 값이 존재하면 출력하고 끝 index까지 갔음에도 불구하고 없다면 -1을 출력한다

 

2개의 for문을 사용하면 O(N^2)의 시간복잡도가 소모되므로 스택을 활용하여 더 빠르게 연산할 수 있다

원래는 스택에 입력받은 값을 차례대로 넣어서 값들을 확인해볼까라는 생각을 하였는데, 해당 방법은

for문 2개 사용하는 것과 큰 차이가 없다는 생각이 들었고, 그래서 stack 리스트를 index 저장용으로

사용하여 코드를 작성하였다 원래 결과값도 매번 append()를 통해 값을 저장하려고 했으나 연산과정이 복잡해져서

-1을 저장한 size크기의 배열로 수정하였다

이후 저장한 index와 현재 index의 값을 비교하여 값을 갱신해주면 된다 

여기서 주의할 점은 stack.append()를 계속해서 수행해주어야 다음 연산을 수행할 수 있다

(stack에 index를 저장하고 있기 때문!)

말로만 보면 헷갈릴 수 있기 때문에 스택을 그리면서 이해하는 것을 추천!

import sys
input = sys.stdin.readline

size = int(input())
NGE = list(map(int, input().split()))

stack = []             # index 저장
result = [-1] * size   # 결과값 저장
for i in range(size):
    while stack and NGE[stack[-1]] < NGE[i]:
        result[stack.pop()] = NGE[i] # 현재 값보다 작은 값을 찾은 경우 값 저장
    stack.append(i)                  # 다음 연산을 위해 append()
    
print(*result)