[백준] 1874번 스택 수열 - 파이썬(Python)

문제 (링크)

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

1874번: 스택 수열

 

나의 풀이

import sys
n = int(sys.stdin.readline())
stack = []
ans = []
count = 1
possible = True

for _ in range(n):
	input_num = int(sys.stdin.readline())
    
    while input_num >= count:
    	stack.append(count)
        ans.append('+')
        count += 1
        
	# count > input_num
    if stack[-1] == input_num:
    	stack.pop()
        ans.append('-')
	
    else:
    	possible = False

if possible:
	for x in ans:
    	print(x)
else:
	print('NO')

 

접근 방법 및 코드 설명

일단 문제 자체가 조금 이해하기 어려웠다.

 

1, 2, 3, 4, ..., n(첫 번째 입력값)을 가지고 두 번째 줄부터 입력되는 숫자들의 순서대로 수열을 완성시켜줘야 한다.

 

첫 번째 입력예시를 살펴보면, 4 3 6 8 7 5 2 1 순으로 수열을 받아오는 걸 확인할 수 있다.

 

이제 1, 2, 3, 4 , .. 순서대로 첫 번째 입력값 8까지의 숫자들을 스택에서 넣고 빼며 위의 배열을 완성해야한다.

 

처음엔 1, 2, 3, 4 를 스택에 넣는다. (+, +, +, +)

 

그 다음, 두 번 pop해줌으로써 수열의 첫 두 부분인 4 3을 완성한다. ( -, -) 이제 스택에는 1, 2만 남는다.

 

아까 4까지 넣었으니 이번엔 5부터 6까지의 수를 스택에 넣어준다. (+, +)그러면 스택엔 1 2 5 6 이 남게 된다.

 

이제 다시 한 번 pop해주어 수열의 6을 만들어준다. ( - ) 이제 스택엔 1 2 5가, 수열은 4 3 6이 담겼다.

 

앞서 6까지 스택에 넣었으니, 이번엔 7부터 8까지 넣어준다. (+, +) 그러면 스택엔 1 2 5 7 8이 남는다.

  

이제 스택에 담긴 나머지 수를 모두 pop 해주고 (-, -, -, -, -) 수열에 담아주면 수열이 완성된다.

 

 

진행 과정을 그대로 코드로 옮기면 된다.

 

    1) 각 수열의 값에 도달할 때까지 1부터 차례대로 스택에 넣고, + 기호를 기록한다.

 

    2) 입력된 수열 값이 차례대로 넣고 있었던 숫자보다 작다면 stack의 가장 위에 해당 수열값이 있는지 찾는다.

 

    3) 만약 맨 위의 값이 해당 수열값과 같다면 pop을 한 후 - 기호를 기록하고, 그게 아니라면 불가능하다고 선언한다.