[파이썬] 백준 알고리즘 No.17298 오큰수

백준 17298번 오큰수 문제

 

 

import sys
input = sys.stdin.readline
n = int(input())
data = list(map(int, input().split()))
token = [-1 for _ in range(n)]

for i in range(n):
    for j in range(i + 1, n):
        if data[i] < data[j]:
            token[i] = data[j]
            break

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

1번째 시도 시간초과 코드

 

 

import sys
input = sys.stdin.readline
n = int(input())
data = list(map(int, input().split()))
token = [-1 for _ in range(n)]
stack = []

stack.append(0)
for i in range(1, n):
    while stack and data[stack[-1]] < data[i]:
        token[stack.pop()] = data[i]
    stack.append(i)
print(*token)

2번쨰 시도 정답 코드

 

 

 

262476KB, 648MS

1번쨰 시도에서 모든 데이터 N개를 N번 비교하여 오큰수를 구하였으므로 시간복잡도는 n의 제곱으로 상승하였다.

따라서 시간 초과가 발생하였다.

 

이를 해결하기 위해서는 조금 더 유연한 사소가 필요하다.

stack을 값이 아닌 인덱스 를 저장하는 매개체로 삼아 복잡도를 대폭 하락시켰다.

i번째 인덱스의 오큰수를 구할 때 마다 stack의 인덱스를 상승시켜 값을 넣어주고, 만약 오큰수를 찾지 못했다면 pass하여 -1로 남긴다.