(Python) - BOJ(1874번) : 스택 수열

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

1874번: 스택 수열

 

---

• 해설 : 

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다.

이 때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다.

임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지,

있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아내는 문제이다.

 

 

 

---

• 풀이 :

수열에 대해 첫 번째 값부터 필요한 만큼의 +(push) 를 수행하고 그 때 스택의 top이 원하는 숫자인 경우 pop()연산을 실행하게 하였다.

만약 스택의 top이 원하는 숫자가 아닌 경우 수열을 만들지 못하므로 NO를 출력하게 하였다.

 

 

 

---

• 소스코드 : 

 

n = int(input())
s = []
op = []
count = 1
temp = True
for i in range(n):
    num = int(input())
    while count <= num:
        s.append(count)
        op.append('+')
        count += 1
    if s[-1] == num:
        s.pop()
        op.append('-')
    else:
        temp = False
if temp == False:
    print('NO')
else:
    for i in op:
        print(i)