[백준 -골드4] 17298번 오큰수(스택, 파이썬)

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

17298번: 오큰수

 

<복습 체크>

22/02/18
O

 

<내 코드>

- n이 최대 100만이기 때문에 시간복잡도가 n^2이면 시간초과가 발생한다.

- 따라서 최대한 n에 가깝게 코드를 구현해야한다.

- for문으로 입력받은 데이터의 모든 원소를 탐색한다.

  - 이때 stack에 원소가 있고, 스택의 마지막 원소보다 해당 데이터의 크기가 클때 while문 수행

     - 스택의 원소를 pop하고, result 배열에 값을 넣어준다.

- 매번 스택에 값을 차례대로 추가한다.

 

예제 입력 동작 순서

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

result = [-1]*n #결과 배열 -1로 초기화
stack = []

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

 

 

<시간 초과 코드>

- 매번 스택 문제에서 나는 아래 방식처럼 해서 틀린다,,,

- 저 방식은 최악의 경우 n(n-1)의 시간복잡도가 나오므로 100만을 제곱하고,, 100만을 빼봐야,,, 시간초과 ㅎ

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))

queue = deque(nums)#큐로 변경
result = []
while queue:
    pop = queue.popleft()
    
    if len(queue)>0:
        check = 0
        for i in range(len(queue)):
            check+=1
            if pop < queue[i]:
                result.append(queue[i])
                break
            if check == len(queue):
                result.append(-1)
result.append(-1)#마지막 원소 처리               
for r in result:
    print(r, end = ' ')