[백준/1874/파이썬] 스택 수열

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

1874번: 스택 수열

조건

• 1~N 까지 수를 스택에 넣었다가, 뽑아서 늘어놓음으로써, 하나의 수열을 만들 수 있다.
• 해당 수열을 오름차순으로 stk에 PUSH,POP을 통해서 만들 수 있는 수열이 있음 .
• 임의의 수열이 주어졌을 떄, 스택을 이용해서 그 수열을 만들 수 있는지 없는지,
• IF possible) 어떤 순서로 push와 pop연산을 수행해야 하는지 알아 낼수 있음.

이 문제는 Stack을 쓰라고 문제 자체에도 나와있음.

Stack을 쓰기위한 문제.

• 문제를 이해 하는게 엄청 어렵다.

문제 이해 자체가 어렵다. 문제를 이해하는데 시간을 되게 많이 쓰게 됨.

이해가 안 가서, 시뮬레이션 해봄.

예제처럼, 4 3 6 8 7 5 2 1 이 입력으로 들어온다고 하자.

그럼, 첫 입력은 4 , 1~4 까지 stack에 넣고,4를 pop

다음 입력 , 3 그럼, 3은 스택의 Top이니까 바로 Pop

다음 입력 6 , 그럼 똑같은 정수는 들어가면 안되니까, 5와 6을 push , 다시 6을 pop stk = [1,2,5]

다음 입력 8 , 7과 8을 push, 8을 pop , stk =[ 1,2,5,7 ]

다음 입력 7 , 7을 만날때 까지 pop

다음 입력 5 , 5를 만날때 까지 pop

다음 입력 2, 2를 만날때 까지 pop

다음 입력 1 , 1 을 만날때 까지 pop

하나하나 따져보면 이런 과정을 거치게 되는것이였음!

• 첫 입력이 오면, 입력까지 수를 stack에 넣어줘야함.ex) input: 4, stk = [1,2,3,4]
• 다음 입력이 스택의 TOP과 같다면, POP
• 다음 입력이 스택의 TOP보다 크다면, stk에 해당 입력까지 값을 넣어주기.
• 그럼, 당연히 TOP에 뭐가 있었는지 , 기억을 해놨다가, Top~입력까지 다시 넣어줘야하는 과정이 필요하므로, 그걸 기억하는 변수가 필요함.
• 다음 입력이 스택의 TOP보다 작다면, 오름차순으로 PUSH를 한 상태인데,
• 당연히 그 값은 TOP 아래 있을거임.
• 그럼, 해당 값을 꺼내기 위해선 pop을 해줘야 하는데, 그럼, 수열이 깨짐. 따라서, 다음 입력이 TOP보다 작다면, 안되는거임.

import sys
input=sys.stdin.readline

n = int(input())
cnt=0 # 기억하는 cnt
ImPossible=False
stk=[]
ans=[]
for i in range(n):
	num = int(input())
	while cnt<num:
		cnt+=1
		stk.append(cnt)
		ans.append('+')
	if stk[-1] == num:
		stk.pop()
		ans.append('-')
	else:
		#flag를 하나 선언해줘서,출력의 구분이 필요함.
		Impossible=True
		break;

if Impossible:
	print('No')
else
	for i in ans:
		print(i)