[python] 백준 1874 - 스택 수열

출처 : 백준, https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

이거 진짜 문제 설명이 이상하다. 나도 잘하는건 아니지만 그래도..........

정답 비율이 낮은 이유가 어려워서가 아니라 문제를 이해 못해서일 확률이 높다.

 

---

1부터 n까지 수를 스택에 차례대로 넣었다 빼면서 입력으로 들어온 순열와 같은 순서를 만들 수 있는가?

단, 스택에서 꺼낸 수는 다시 넣을 수 없고 꺼낸 순서대로 별도로 나열되어 있어야한다.

스택에 수를 넣고 빼는 것을 반복해 스택에서 꺼낸 수의 순서가 입력 순열의 순서와 일치하도록 만들 수 있다면

+- 기호를 통해 순서를 출력하고, 없다면 NO를 출력해라.

 

이 때, 입력으로 들어오는 숫자열은 스택에 쌓여있는 형태로 주어진다.

(예제 1 -> (top) 4 3 6 8 7 5 2 1 (bottom))

즉, 스택에서 뺴면 4 3 6 8 7 5 2 1와 같은 순서가 되도록 만들면 된다.

---

 

 

풀이

 

if __name__ == '__main__':
  string = []
  stack = []
  arr = []

  n = int(input())

  wait_list = [i for i in range(n, 0, -1)]

  for i in range(n):
    string.append(int(input()))

  string = string[::-1]

  stack.append(wait_list.pop())
  arr.append('+')

  while len(wait_list) or len(stack):
    if len(stack) == 0 or stack[-1] < string[-1]:
      num = wait_list.pop()
      stack.append(num)
      arr.append('+')
    elif stack[-1] == string[-1]:
      stack.pop()
      string.pop()
      arr.append('-')
    else:
      break

  if string == stack:
    for char in arr:
      print(char)
  else:
    print('NO')

 

---

 

시간 복잡도

 

-

 

알게 된 점

 

-

 

고찰

 

-