백준 1874 - 스택 수열 (python)
2023. 7. 28. 05:13ㆍ알고리즘
문제
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
풀이
n = int(input())
a = [int(input()) for _ in range(n)]
st = []
cmd = []
idx = 0
next = 1
while idx <len(a):
if next <= a[idx]:
st.append(next)
cmd.append('+')
next +=1
elif st[-1] == a[idx]:
st.pop()
cmd.append('-')
idx += 1
else:
cmd = ['NO']
break
print('\n'.join(cmd))스택에 1~N까지의 수를 직접 넣어보며 가능한지 여부를 판단한다.
st가 스택
cmd가 출력할 내용 (+, -, NO)
idx가 입력받은 수열과 비교중인 위치
next가 다음에 push될 숫자
while문을 돌면서 수열의 모든 요소와 비교할 때 까지 stack에 push하고 pop 하는 과정을 반복한다.
도중에 push나 pop으로 수열을 만들 수 없을 경우에는 cmd에 NO를 저장한뒤 바로 break 시켜서 NO를 출력해준다.