임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
문제는 완전히 이해했는데 반복문 탈출조건 설정이 까다로워 해결하지 못했다. 이틀 간 풀었는데 처음 작성한 코드는 문제에서 주어진 테스트 케이스는 모두 통과했지만 질문검색에서 얻은 예외 케이스 push, pop이 연속해서 나오는 경우 오류가 발생하였다. 그래서 수정한 아래 두번째 코드는 예외 케이스와 해피 케이스 모두 만족하지만 수열을 만들지 못하는 경우 무한루프가 돌고 만다. 너무 오래 붙잡은 것 같으니 다른 사람의 코드를 참고해보자.
# 오류코드
from collections import deque
n = int(input())
operators = [] # 연산
sequence = deque() # 수열
numbers = [] # (1~n)까지의 숫자
top = 0
for i in range(n):
sequence.append(int(input()))
number = 1
while numbers or top != n:
# push
numbers.append(number)
operators.append("+")
number += 1
while numbers[-1] == sequence[top]: # pop
numbers.pop()
operators.append("-")
top += 1
if not numbers:
break
if top != n:
print("NO")
else:
for i in operators:
print(i)# 참고코드
연속해서 pop() 하는 경우 while문 탈출 조건을 세우기 애매해서 그 부분을 참고하려고 했는데 구조가 달랐다. 가장 다른 부분은 수열 입력을 한번에 받는 게 아니라 하나씩 받아서 받을 때마다 처리했다. 생각해보니 그렇다. 내가 수열을 처리할 때도 index변수 하나를 두거나 수열리스트를 pop해줬는데 넣고 뺄 필요 없이 아예 하나씩 체크하면 되었다. 주어진 데이터라고 무조건 리스트에 저장할 생각부터 하지 말자!
while cur <= num: : stack top이 num보다 작은 경우 스택에 쌓인다.
if stack[-1] == num: : stack top과 num이 같다면 수열을 만들 수 있다.
else:: stack top이 num보다 큰 경우 num은 top보다 아래 쌓여있기 때문에 수열을 만들 수 없다.
n = int(input())
stack = []
answer = []
flag = 0
cur = 1
for i in range(n):
num = int(input())
while cur <= num:
stack.append(cur)
answer.append("+")
cur += 1
if stack[-1] == num:
stack.pop()
answer.append("-")
else:
print("NO")
flag = 1
break
if flag == 0:
for i in answer:
print(i)pop() == pop(0) ?
추가적으로 시간복잡도를 생각하며 코드를 짜다보니 리스트에서의 pop()과 pop(0)의 시간복잡도가 다르다는 것을 알았다. 맨뒤, 맨앞에서 빼니까 똑같은 줄 알았는데 pop()은 O(1)이고 pop(0)은 리스트 전체를 복사해서 O(N)이다. 맨앞의 원소를 빼야한다면 deque()를 사용해서 맨앞의 원소도 O(1)로 가져올 수 있다.
