백준 1874: 스택 수열

✔ 풀이를 위한 아이디어

• 직접 push/pop 하지 않고 index로 접근하기
  
  

✔ 코드

import sys

n = int(sys.stdin.readline())
want = [int(sys.stdin.readline()) for _ in range(n)]

current_index = 0
answer_list = []
answer_list.append('+')
stack = [i+1 for i in range(n)]
black_list = [0] * n

i = 0
while i < n:
    if want[i] > stack[current_index]:
        answer_list.append('+')
        current_index += 1
        while black_list[current_index] == 1:
            current_index += 1
    elif want[i] == stack[current_index]:
        answer_list.append('-')
        black_list[current_index] = 1
        while black_list[current_index] == 1:
            if current_index > 0:
                current_index -= 1
            else:
                break
        i += 1
    elif want[i] < stack[current_index]:
        print("NO")
        sys.exit()
        
for i in range(len(answer_list)):
    print(answer_list[i])

• 미리 n개의 숫자를 배열에 넣어둔 뒤에, current_index라는 변수만 왔다갔다 하면서 push와 pop의 기능을 대신하도록 짜보았다.
• 이때, pop으로 인해 없는 것으로 간주되어야 하는 요소를 관리하기 위해 black_list라는 배열을 도입하였다.
• want[i]가 stack[current_index]보다 작아졌을 때가 그 수열을 만들 수 없는 경우에 해당한다는 것을 알아야한다.
• 자료구조 수업 때 짰던 스택은 실제로 push와 pop을 했어야 하는데, 오히려 시간복잡도를 줄이기 위해서 그러한 기능을 구현하지 않게 되었다.
  
  

• 동일한 코드인데 Python3로 했을 때는 안되고, PyPy3로 했을 때는 되었다.
  Python3과 PyPy3의 차이점: https://ralp0217.tistory.com/entry/Python3-%EC%99%80-PyPy3-%EC%B0%A8%EC%9D%B4
  
  

✔ 관련 개념

• 스택