[백준] 17298번 : 오큰수 (Python)

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

 

오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다.

이 문제는 수열의 각 원소 Ai의 오큰수, NGE(i)를 구하는 문제다.

 

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
now = list(map(int, input().split()))
answer = [0]*N

mydeq = deque() # stack 선언

for i in range(N):

    # 빈 상태일 시 append
    if not mydeq:
        mydeq.append(i)
        continue

    # 덱의 마지막 위치에서부터 현재 값보다 작은 값은 덱에서 제거
    while mydeq and now[mydeq[-1]] < now[i]:
        pop_index = mydeq.pop()
        answer[pop_index]= now[i]

    # 오큰수 저장
    mydeq.append(i)


for i in mydeq:
    answer[i]=-1

for i in answer:
    print(i, end=' ')

 

 

 

[문제풀이]

---

 

이 문제는 반복을 이용해 쉽게 구현할 수 있지만, 시간복잡도가 너무 커지고 만다. 어떻게 하면 반복을 사용하지 않고 O(nlogn) 시간 복잡도 안에 오큰수를 구할까를 푸는 문제다.

 

stack으로 어떻게 구현할까가 핵심 아이디어!

 

• 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.

 

이 아이디어에 따라 스택으로 오큰수를 구현하면 이렇다.

 

 

 

1. 스택이 채워져 있거나 A[index] > A[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장. 단, 이때 pop는 조건을 만족하는 동안 계속 반복.
2. 현재 인덱스를 스택에 push(append)하고 다음 인덱스로 넘어감
3. 과정 1~2를 수열 길이만큼 반복한 다음 현재 스택에 남아 있는 인덱스에 -1를 저장