백준 1874 스택 수열

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

1874번: 스택 수열

 

문제 이해와 단계별 풀이

문제를 이해하면 쉽게 느껴지지만 풀기전에 생각해야 하는 몇몇 부분들이 있다. 우선, 입력 받은 스택이 가능한지 수학적인 공식이나 간단한 정리로 판별하기 굉장히 어려워 보인다. 따라서 문제에서 주어진 스택 기능을 그대로 따라하면서 가능한지 확인을 해야 하며 당연히 입력을 받을 때마다 이를 판별해야 한다. 그럼 해당 스택을 구현하기 위한 stack =[]과 입력 정답을 저장할 배열 answer =[]가 필요하고 입력 받을 변수 n이 필요하다. 그렇다면 해당 변수 n이 스택 가능한지 또 가능하다면 이를 answer에 어떻게 반영을 하냐? 이 부분이 문제의 핵심이 될것이다. 이를 위해 다음 그림을 통해서 설명을 하겠다.

지금까지의 설명으로 왼쪽의 코드를 어렵지 않게 생각할 수 있다. 여기서 문제에서 주어진 입력 예시로 num=4부터 생각하여 stack, answer, num의 관계를 살펴보자. stack에는 입력 받은 num에 따라 1부터 증가하여 배열에 쌓이고 answer에 '+'를 입력한다. 정확하게 입력 받은 수 n까지 이를 수행한다. 때문에 우리는 num을 비교할 count라는 변수를 도입하고 이를 1씩 증가하여 num보다 커지면 더 이상 stack과 answer에 대한 작업을 수행하지 않게 한다. 같은 논리로 '-'를 입력해야 하는 경우를 생각하자

지난 입력이 num=4라는 것을 생각하면 4는 이후에 pop을 해야한다. 즉 첫 번째 입력 이후에 즉각적으로 4를 pop, answer.append('-')를 수행. 이후에 num=3을 입력하면 또 3을 pop, answer.append('3')을 수행하며 이를 입력 받은 수 num까지만 수행. 그렇다면 num과 비교할 수는 무엇인가? 그림의 상황 이후에는 num=6이라 answer에 ++++-- '+'가 오게 된다. 즉, stack[-1]에 따라서  '-'를 append

이 모든 조건에 해당이 되지 않는다면 당연히 stack이 불가능하므로 지금까지의 정리를 바탕으로 코드를 짜면 다음과 같이 된다.

 

문제 풀이

n = int(input())
stack = []
answer = []
count = 1
possible = True
for i in range(n):
  num = int(input())
  while count <= num:
    stack.append(count)
    answer.append('+')
    count += 1
  if num == stack[-1]:
    stack.pop()
    answer.append('-')
  else:
    possible = False
    break
if possible == False:
  print('NO')
else:
  for i in range(len(answer)):
    print(answer[i])