[Algorithm] 백준 #1874 - 스택 수열

 

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

 

🔎 어려웠던 점

1. "스택에 push하는 순서는 반드시 오름차순을 지키도록 한다." 라는 말이 이해가 어려웠다.

 

즉, 문제 예시처럼 수열에 4를 첫번째로 나오게 하기 위해서는, 1~3까지의 수를 push하고 4을 push하고, 4을 pop해줘야 한다.

 

2. 수열을 만들 수 없는 경우를 stack 그림을 통해서는 대략(?) 이해가 갔지만, 코드로 직접 표현하는 부분이 어려웠다. 

---

스택을 만들 수 있는 경우

 

예시

• 1 ~ 4를 push 하고, 4와 3을 순차적으로 pop시켜 수열에 넣는다.
• 수열에 6을 넣기 위해서는 스택에 5와 6을 push하고 6을 pop시킨다.
• 동일한 과정으로 수열에 8을 넣기 위해서는 7과 8을 push하고 8, 7을 pop시킨다.
• 스택에 남아있는 숫자를 차례대로 pop해주면 5 2 1이 나온다.

 

 

 

스택을 만들 수 없는 경우

두번째로 주어진 예제는 만들수 없는 수열이다.

5까지 수열에 넣고 나머지 숫자들을 pop해주면 3과 4의 순서가 반대로 나와 정답과 다르기 때문이다.

 

 

 

num, start	stack	start 갱신
num = 1, start = 1	[1]	2
num = 2, start = 2	[2]	3
num = 5, start = 3	[3]	4
num = 5, start = 4	[3, 4]	5
num = 5, start = 5	[3, 4, 5]	6

 

stack[-1] == num이므로 (5로 동일) 스택에서 pop시켜준다. 

 

num, start	stack	start 갱신
num = 3, start = 5	[3, 4]

 

수열에 3을 넣어주려는데, stack[-1]값인 4와 num값인 3이 달라 수열을 만들어줄 수 없다. 

스택의 맨 위에 있는 숫자와 num이 일치해야지만 pop을 시켜 수열에 넣어줄 수 있다. 

 

import sys
input = sys.stdin.readline
stack = []
operator = []
flag = True

N = int(input())
start = 1

for i in range(N):
    num = int(input())
    while start <= num:  # 스택에 숫자 push
        operator.append("+")
        stack.append(start)
        start += 1

    if stack[-1] == num:  # 스택에서 꺼내기(pop)
        stack.pop()
        operator.append("-")
    else:
        print("NO")
        flag = False
        break

if flag:
    for i in operator:
        print(i)