#1874 스택수열 [백준](H99.29)

📄문제

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

예제 입력1

8
4
3
6
8
7
5
2
1

예제 출력1

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

🖋️코드

n = int(input())
stack = []
result = []
count = 0
poss = True

for _ in range(n):
    num = int(input())
    while count < num:
        count += 1
        stack.append(count)
        result.append('+')
    if stack[-1] == num:
        stack.pop()
        result.append('-')
    else:
        poss = False
        break

if poss == False:
    print('NO')
else:
    for i in result:
        print(i)

🧷(나만 알아듣는) 추가설명

예제 입력으로 예를 들어서 process를 본다면
8을 입력해서 1~8까지 들어온다는 걸 알았다
[ 4 , 3 , 6 , 8 , 7 , 5 , 2 , 1 ] 순서로 만들어야한다면 첫 숫자가 4 이니까
for문으로 1 , 2 , 3 , 4 순으로 '+'하면서 4가 들어오면 stack =[ ]에 pop 해준다
stack = [4] 가 되겠고, result에 '-'가 result = ['+', '+' , '+' , '+' , '-'] 이렇게 들어온다

이후 이미 3이 끝에 있기때문에 1, 2, 3에서 3을 똑같이 stack과 result에 넣어준다
그럼 각각 stack= [4 , 3] result=['+', '+' , '+' , '+' , '-', '-'] 가 있고 다시 숫자가 들어온다
1 , 2 , 5 , 6이 들어오면 6을 또 넣어주고

이렇게 해서 원하는 수열이 만들어질수 있다면 result를 print
안만들어진다면 'NO'를 print하면 된다.