[파이썬/python] 백준 1874 - 스택 수열

문제

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

---

문제 설명

1.   1부터 n까지 수를 스택에 넣고 늘어놓으면, 하나의 수열을 만들 수 있다.
   1. 스택에 push할 때, 순서는 반드시 오름차순으로한다.
2. 임의의 수열의 숫자가 한 개씩 순서대로 주어진다.
3. 스택을 통해 그 수열을 만들 수 있는지 없는지, 확인해야 한다.
4. 주어진 수열을 만들 수 있을 때 push와 pop연산을 어떤식으로 수행해야 하는지 계산하여 출력한다.

 

---

풀이

1. 수열의 한 숫자 t를 입력받았을 때 현재 count의 수 만큼 stack을 채운다.
   1. 스택은 1부터 n까지 순차적으로 입력한다. 따라서 count의 수는 현재 $n_i$번째 수까지 넣었음을 의미한다.
   2. t가 count보다 크거나 같다면 스택에 숫자를 추가하고 결과에 '+'를 추가한다. 
   3. t가 count보다 작다면 이미 t는 stack에 존재하므로 while문을 탈출한다.
2. 현재 스택에서 탈출 가능한 숫자가 t와 같다면 stack에서 꺼내고 결과에 '-'를 추가한다.
   1. 이 때 stack[-1]이 t와 다르다면 해당 수열을 만들 수 없으므로 flag = 0으로 변경하고 탈출한다.
3. 최종 결과를 출력한다.

---

코드

import sys
input = sys.stdin.readline

stack = []
res = []                
count=1

n = int(input())
flag = 1

for i in range(n):
    t = int(input())       

    while count <= t :
        stack.append(count)
        res.append('+')
        count+=1

    if stack[-1] == t:
        stack.pop()
        res.append('-')
    else:
        flag = 0
        print('NO')
        break
 
if flag:
    for i in res:
        print(i)

---

시간복잡도

• 최악의 경우 N = $10^5$
• 최대 N만큼 반복하므로 약 O(N)의 시간복잡도가 소요된다.