스택 수열

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

 

---

나의 코드

import sys
input = sys.stdin.readline

from collections import deque
ct = int(input())
queue = deque()
for _ in range(ct):
    queue.append(int(input()))
    
stack = []
result = []
for i in range(1, ct+1):
    stack.append(i)
    result.append('+')
    
    if stack[-1] > queue[0]:
        result = ['NO']
        break
    
    while stack and queue and (stack[-1] == queue[0]):
        result.append('-')
        stack.pop()
        queue.popleft()

if queue:
    result = ['NO']
    
for i in result:
    print(i)

 

---

시간 복잡도

for _ in range(ct) : queue를 생성 ( 선형 시간 복잡도 )
for i in range(1, ct+1) : 스택을 push 해주며 조건에 맞는 수 스택 과 큐 에서 제거 ( 선형 시간 복잡도 )
for i in result : 최종 결과값을 순회하며 print ( 션형 시간 복잡도 )

해당 알고리즘 시간복잡도는 선형 시간 복잡도 ( O(n) )