[백준] 1874번: 스택 수열

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

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

---

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

---

예제입력1

8
4
3
6
8
7
5
2
1

예제출력1

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

 

---

예제입력2

5
1
2
5
3
4

예제출력2

NO

---

문제풀이 

n=int(input())

stack=[]

op=[]

count=1     #1부터 n까지의 수를 스택에 넣었다가 뽑는데, 그 수 n을 처음 count 1로 하는거다.

temp=True

먼저 설계를 해보자. stack이라는 리스트에 각 숫자를 append했다가 pop하고, push와 pop을 할 때마다 op라는 리스트에 +와 -를 대입시킨다. 연산이 불가능한 경우에 NO를 출력하기 위해 temp라는 bool자료형을 설정하고, while문을 통해 입력한 숫자만큼 append해야하니, count=1을 설정한다. 

 

for i in range(n):

    num=int(input())

    while count<=num:   # 4를 입력받으면 1부터 4까지 넣어야 하니까 <= 부등호를 사용한다.

        stack.append(count)

        count+=1

        op.append("+")

    if stack[-1]==num:

        stack.pop()

        op.append("-")

    else:

        temp=False

        break

위의 코드를 예시를 통해 설명하자. 

4를 입력받으면 1,2,3,4를 stack에 append한다. count도 4가 된다.

이후 4를 pop해야 하니 4를 pop한다.

3을 입력받으면 count가 num보다 크다.

그러니 다음 if문으로 넘어가서 stack에 제일 위에 있는 수가 3과 동일하니 3을 pop한다.

6을 입력받으면 count가 4이니 5,6을 stack에 append하고

6이 stack제일 위에 있으니 pop한다.

그럼 stack에 1,2,5가 들어있는데 이때 2를 입력하면 2를 pop하기 전에 5가 pop되어야 한다. 그러니 연산불가하니 그때는 temp를 False로 바꾼다. 

 

if temp==False:

    print("NO")

else:

    for i in op:

        print(i)

temp가 False인 경우 NO를 print하고

아니면 op의 요소들을 순서대로 print한다. 

 

정답

n=int(input())
stack=[]
op=[]
count=1     #1부터 n까지의 수를 스택에 넣었다가 뽑는데, 그 수 n을 처음 count 1로 하는거다. 
temp=True
for i in range(n):
    num=int(input())
    while count<=num:   # 4를 입력받으면 1부터 4까지 넣어야 하니까 <= 부등호를 사용한다. 
        stack.append(count)
        count+=1
        op.append("+")
    if stack[-1]==num:
        stack.pop()
        op.append("-")
    else:
        temp=False
        break
if temp==False:
    print("NO")
else:
    for i in op:
        print(i)