문제설명
n개의 수로 이루어진 수열을 입력받아서 1부터 n까지의 수를 스택에 넣었다가 빼서 그 수열을 만들기위해서는 어떻게 연산을 하여야하는지 출력하는 문제입니다. 만약 만들 수 없을 경우 0을 출력합니다.
작동 순서
1. n을 입력받고 n개의 수열을 입력받습니다.
2. 반복문을 이용해서 가장 먼저 빼야할 숫자까지 스택에 넣고 +를 출력 리스트에 넣어줍니다.
3. 가장 먼저 빼야할 숫자를 스택에서 pop하고 -를 출력 리스트에 넣어줍니다.
4. 그 다음으로 출력해야할 숫자까지 append 해주거나 그 숫자가 이미 stack에 있을 경우 pop을 해줍니다.
5. 만약 pop을 순서대로 했을 때 입력된 수열과 맞지 않을 경우 NO를 출력하고 프로그램을 종료합니다.
6. 입력된 수열과 맞게 모든 연산을 완료하면 출력 리스트에 들어있는 연산 순서를 출력해줍니다.
소스코드
import sys
n = int(sys.stdin.readline())
stack = []
input_num = []
output = []
num = 0
pop = 0
fail = False
for i in range(n):
input_num.append(int(sys.stdin.readline()))
while pop < n:
while num < input_num[pop]:
num += 1
stack.append(num)
output.append("+")
while num >= input_num[pop]:
output.append("-")
if stack.pop(-1) != input_num[pop]:
fail = True
break
pop += 1
if pop == n:
break
if fail:
print("NO")
break
if not fail:
for i in range(len(output)):
print(output[i])
후기
스택을 사용한 간단한 문제입니다. 스택방식을 사용하지 않고 수열과 n만을 이용해서 풀어보려 했지만 실패하고 결국 스택을 사용하여 풀었습니다. 꼭 복잡한 수식이 최선은 아닌 것 같습니다.