스택 #백준 1874

www.acmicpc.net/problem/1874

1874번: 스택 수열

[ 문제 해결 방법 ]

 

처음 문제를 보고 무슨말인지 하나도 이해하지 못하였다.. 결국 인터넷 검색을 통하여 문제를 이해하였다.

 

8 4 3 6 8 7 5 2 1

 

위와 같이 입력을 받는다고 하자.

 

n이 8이고 수열 = [4, 3, 6, 8, 7, 5, 2, 1] 이 된다.

 

그럼 이제 1 부터 8 까지 오름차순으로 숫자를 받아서 스택을 활용해 수열 = [4, 3, 6, 8, 7, 5, 2, 1]을 만들어 주면 된다.

 

우선 스택에 push를 먼저 하면 1이 담긴다.

 

s = [1]

 

한번 더 push를 하면 2가 담긴다.

 

s = [1, 2]

 

이런식으로 push를 4번해주면

 

s = [1, 2, 3, 4]가 담긴다.

 

여기서 입력받은 수열과 같게 하려면 pop을 두번 해주면

 

[4, 3] 이렇게 담겨진다.

 

이런식으로 push와 pop을 해가며 pop을 이용해 입력받은 수열([4, 3, 6, 8, 7, 5, 2, 1])을 만드는 것이다.

 

문제만 이해한다면 쉽게 풀 수 있다.

 

[ 소스코드 ]

n = int(input())
s = []
op = []
count = 1
temp = True
for i in range(n) :
  num = int(input())

  while count <= num :
    s.append(count)
    op.append("+")
    count += 1
  
  if s[-1] == num :
    s.pop()
    op.append("-")
  else :
    temp = False
    break

if temp == False:
    print('NO')
else:
    for i in op:
        print(i)