Coding/백준
[백준] 10828 - 스택 수열 - (python 파이썬)
Coding Kitsune
2022. 2. 1. 22:50
문제링크 : https://www.acmicpc.net/problem/1874
1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
www.acmicpc.net
풀이과정:
문제를 이해하는것이 정말 어려웠다...
스택에 1,2,3......순서로 계속해서 쌓아두고 차례로 뽑아쓰는 개념이다.
문제 처럼 4, 3, 6, 8 순서로 이 스택에서 뽑아쓰고 싶다면
스택을 먼저 만든다. 스타트가 4이기 때문에
[1, 2, 3, 4] 의 수열을 만들고, 내가 원하는 숫자 4를 pop한다.
그럼 스택에 남은 수는 [1, 2, 3] 이 될것이다. 이제 내가 원하는 숫자는 3
그럼 또 3을 pop한다. 이제 수열에는 [1, 2]의 숫자만 남는다.
이제 내가 필요한 숫자는 6인데 이 스택에 존재하지않는다.
그럼 다시 4 이후의 숫자부터 내가 필요한 숫자까지 스택을 만든다.
스택이 [1, 2, 5, 6]이 되었고 내가 필요한 수 6을 뽑아 스택이 [1, 2, 5]가 된다.
같은 방식으로 스택을 [1, 2, 5, 7, 8]까지 제작하고 8을 뽑아쓰는 매커니즘으로
반복하면 되고 이 논리대로 코드를 작성하면 된다.
n = int(input())
lst = []
op = []
series_num = 1
flag = True
for _ in range(n):
num = int(input())
while series_num <= num:
lst.append(series_num)
op.append('+')
series_num += 1
if lst[-1] == num:
lst.pop()
op.append('-')
else:
flag = False
break
if flag == False:
print('NO')
else:
for i in range(len(op)):
print(op[i])
