백준 1874번. 스택 수열 (Python / 파이썬)

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

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

출력

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

---

문제 풀이

문제를 풀기 위해 먼저 Stack 자료구조에 대한 이해가 필요합니다.

Stack은 LIFO(Last in First out) 구조로 제일 나중에 넣은 원소가 제일 먼저 나오게 되는 구조입니다.

탑 쌓기로 Stack 자료구조를 생각하면 쉽게 이해할 수 있습니다.

1번 블록을 제일 아래에, 나머지 2, 3, 4번 블록을 차례로 쌓았다고 할 때 중간에 있는 블록부터

꺼내면 탑이 무너집니다. 따라서 무조건 제일 위에 있는 4번부터 차례로 블록을 내려야 합니다.

 

이러한 Stack 자료구조의 특징을 이용해 문제를 해결할 수 있습니다.

문제의 예제1로 설명해보면, 4 3 6 8 7 5 2 1이 차례로 입력된다 할 때

4가 입력되면 Stack에는 무조건 4까지 원소를 쌓아야 합니다. (그래야 4를 꺼낼 수 있기 때문)

따라서 count 변수를 이용해 Stack에 원소를 4까지 쌓아줍니다.

그리고 삽입할 때마다 +기호를 결과 list에 저장해줍니다.

만약 Stack의 제일 위의 원소가 입력한 수와 같다면 pop() 연산을 이용해 꺼내줍니다.

그리고 - 기호를 결과 list에 저장해줍니다.

3은 count보다 작으므로 이미 삽입되었다는 것을 알 수 있습니다. 따라서 바로 제일 위의 원소가

3인지 확인하고 만약 같다면 pop() 연산을 이용해 꺼내줍니다.

이때, 만약 제일 위의 원소가 3이 아니라면 3은 절대로 그 다음 순서로 꺼낼 수 없습니다.

따라서 No를 출력하도록 해줍니다.

나머지 과정도 이와 같이 수행해주면 결과를 쉽게 출력할 수 있습니다.

---

My Code

n = int(input())

stack = []
result = []
count = 0
check = True
for _ in range(n):
  num = int(input()) 
  if count < num: # 입력된 수가 더 크면
    while count != num: # 입력된 수와 같을 때까지
      count += 1        # 카운트를 증가시켜
      stack.append(count) # 차례로 삽입
      result.append('+')  # 삽입할 때마다 +기호 삽입
  
  if num == stack[-1]: # 가장 위 원소가 입력된 수와 같다면
    stack.pop()        # 삭제
    result.append('-') # 삭제할 때마다 -기호 삽입
  else: # 가장 위의 원소가 입력된 수가 아니라면
    check = False # 절대 꺼낼 수 없으므로 False로 만들어줌

if check: # 입력된 수열을 만들 수 있다면
  for i in result: # 결과 출력
    print(i)
else:     # 만들 수 없다면
  print('NO') # NO 출력