[백준] 1874번 스택 수열

⛏ 문제 파악

• 문제 이해가 어려웠던 문제이다. 스택의 후입선출(LIFO, Last-In First-Out)을 생각하면 이해가 괜찮아지는 문제다.
• 입력은 오름 차순으로 이루어지고, 입력을 받을 때마다 다음의 상황을 고려하면서 풀면 된다.
  • 내가 입력하려는 수가 수열에 넣어야하는 수와 같다면, 스택에 push하고 pop 해준다.  이 때 수열에 넣어야하는 수와 스택에 있는 수가 같다면 계속해서 pop을 해준다.
  • 내가 입력하려는 수가 수열에 넣어야하는 수와 다르다면 스택에 push만 한다.
• 예시로 주어진 테스트 케이스 1번을 천천히 살펴보면서, 문제를 설명해보겠다.
  1. 스택에 push 하면 스택은 [ 1 ] 이고, 수열 [ 4, 3, 6, 8, 7, 5, 2, 1 ] 에서 4와 다르므로 패스
  2. 스택에 push하면 스택은 [ 1, 2 ] 이고, 수열 [ 4, 3, 6, 8, 7, 5, 2, 1 ] 에서 4와 다르므로 패스
  3. 스택에 push하면 스택은 [ 1, 2, 3] 이고, 수열 [ 4, 3, 6, 8, 7, 5, 2, 1 ] 에서 4와 다르므로 패스
  4. 스택에 push하면 스택은 [ 1, 2, 3, 4 ]이고, 수열 [ 4, 3, 6, 8, 7, 5, 2, 1 ] 에서 4와 같으므로 스택을 pop
     • 그러면 스택은 [ 1, 2, 3]이고, 수열 [ 4, 3, 6, 8, 7, 5, 2, 1 ]에서 3과 같으므로 스택을 pop
     • 스택 [ 1, 2]이고, 수열 [ 4, 3, 6, 8, 7, 5, 2, 1 ]에서 6과 다르므로 패스
  5. 스택에 push 하면 [ 1, 2, 5]이고 수열 [ 4, 3, 6, 8, 7, 5, 2, 1 ]에서 6과 다르므로 패스
  6. 스택에 push 하면 [ 1, 2, 5, 6 ]이고 수열  [ 4, 3, 6, 8, 7, 5, 2, 1 ]에서 6과 같으므로 스택을 pop
     • 그러면 스택이 [ 1, 2, 5 ]이고 수열  [ 4, 3, 6, 8, 7, 5, 2, 1 ] 에서 8과 다르므로 패스
  7. 스택에 push하면 [ 1, 2, 5, 7 ]이고 수열  [ 4, 3, 6, 8, 7, 5, 2, 1 ]에서 8과 다르므로 패스
  8. 스택에 push하면 [ 1, 2, 5, 7, 8]이고 수열  [ 4, 3, 6, 8, 7, 5, 2, 1 ]에서 8과 같으므로 pop
     • 스택 [ 1, 2, 5, 7]이고 수열  [ 4, 3, 6, 8, 7, 5, 2, 1 ] 에서 7과 같으므로 pop
     • 스택 [ 1, 2, 5 ] 이고 수열  [ 4, 3, 6, 8, 7, 5, 2, 1 ]에서 5와 같으므로 pop
     • 스택 [ 1, 2 ] 이고 수열  [ 4, 3, 6, 8, 7, 5, 2, 1 ]에서 2와 같으므로 pop
     • 스택 [ 1 ] 이고 수열  [ 4, 3, 6, 8, 7, 5, 2, 1 ]에서 1과 같으므로 pop
• 이러한 방식으로 두번째 테스트 케이스틀 보면, top과 수열에 넣어야하는 수가 맞지 않아서 만들 수 없는 수열이라는 것을 발견할 수 있다.

 

👉🏻  답안

import sys
K = int(sys.stdin.readline())

model = []
stack = [0]
results = []
count = 0
message = 0

for _ in range(K):
  model.append(int(sys.stdin.readline()))

for i in range(K):
  if stack[-1] < model[i]:
    while count < model[i]:
      count += 1
      stack.append(count)
      results.append('+')
    stack.pop()
    results.append('-')
  elif stack[-1] == model[i]:
    stack.pop()
    results.append('-')
  else:
    message -= 1
    break

if message == -1:
    print("NO")
else:
  for result in results:
    print(result)

📑  간단한 설명

• 위에서 설명을 많이 해놓았다..
• 그냥 그것을 코드로 만들어 놓은 것이다.
• 아 스택에 [ 0 ] 을 넣은 것은 stack [-1]이 오류가 나지 않기 위해서다.