[Baekjoon] 17298번 : 오큰수 (Python)

Python

시간초과 - 코드 길이 361B

stack이 아닌 2중 for문으로 문제를 풀면 다음과 같다.

단순히 값들에 대한 단순 인덱스별 값을 비교하기 때문에 이는 시간초과와 연결된다.

고로 이를 해결하기 위한 방법이 필요하다.

import sys
input = sys.stdin.readline
n=int(input())
l = list(map(int, input().split()))

ans = []
for i in range(n):
    s = []
    flg = 0
    for j in range(i+1,n):
        s.append(l[j])
        if l[j] > l[i]:
            ans.append(s.pop())
            flg = 1
            break
    if flg == 0:
        ans.append(-1)

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

방법 1 - 메모리 149424KB / 시간 1228ms / 코드 길이 244B

시간 초과를 해결하기 위해 사용할 수 있는 방법은 stack이다.

stack에는 인덱스를 저장하고 NGE에는 -1로 초기화된 값들을 저장한다.

위 코드에서는 일일이 위치별 값들에 대한 비교를 진행했지만 본 방법에서는 stack에 우리가 NGE라 불리는 값들에 도달할 수 있는 곳까지 인덱스를 저장한 후 조건이 맞다면 NGE의 값들을 수정하는 방식으로 반복문이 진행된다.

가령 예를 들어 [9,5,4,8]이라는 숫자가 있다.

초기 값 NGE = [-1, -1, -1, -1], stack = []

i = 0

stack이 비어있다. 조건문에 부합하지 않다.

NGE = [-1, -1, -1, -1], stack = [0]

i = 1

stack에 값은 존재하나 l[0]=9 < l[1]=5에 부합하지 않는다.

NGE = [-1, -1, -1, -1], stack = [0, 1]

i = 2

stack에 값은 존재하나 l[1]=5 < l[1]=4에 부합하지 않는다.

NGE = [-1, -1, -1, -1], stack = [0, 1, 2]

i = 3

stack에 값은 존재하고, l[2]=4 < l[3]=8에 부합한다.

NGE = [-1, -1, 8, -1], stack = [0, 1]

stack에 값은 존재하고, l[1]=5 < l[3]=8에 부합한다.

NGE = [-1, 8, 8, -1], stack = [0]

stack에 값은 존재하나 l[0]=9 < l[3]=8에 부합하지 않는다.

NGE = [-1, 8, 8, -1], stack = [0, 3]

for문 완료

NGE 출력

import sys
input = sys.stdin.readline

n = int(input())
l = list(map(int, input().split()))

NGE = [-1] * n
stack = []

for i in range(n):
    while stack and l[stack[-1]] < l[i]:
        NGE[stack.pop()] = l[i]
    stack.append(i)

print(*NGE)