[백준/BOJ] - 18111번 python 풀이

---

문제 이해하는데 오래걸린 문제.

쉽게 정리하면

1부터 n까지 스택에 push 하며 주어진 수열에 알맞은 순서로 pop을 하면 되는 문제이다.

예시) 43687521

+ (1)

1

+ (2)

12

+ (3)

123

+ (4)

1234

- (4)         4는 (주어진 수열의 맨 처음 값)은 deque(주어진 수열)에서 제거된다.

123 

.

.

.

 

집중이 안 되서 생각 나는데로 풀었다.

---

Key Point

- 맨처음 입력되는 값은 deque 자료구조를 활용하여 시간 복잡도를 줄였다.

 

---

import sys
from collections import deque
input = sys.stdin.readline
queue = deque([])

ex = []
n = int(input())
lists1 = []
printing = []
for i in range(n):
    queue.append(int(input())) # 43687521
#queue[0]
num = 1
i = 0
flag = 0
while True:  
    if len(ex) != 0:
        if queue[0] == ex[-1]:
            ex.pop()
            queue.popleft()
            printing.append('-')
            flag = 1
        
    if flag != 1 and queue[0] != num:
        ex.append(num)
        printing.append('+')
        flag = 2
    elif flag != 1 and queue[0] == num:
        queue.popleft()
        printing.append('+')
        printing.append('-')
        flag = 2
    
    if flag != 1:
        num+=1

    flag = 0

    if len(queue) == 0:
        break
    
    if len(ex) != 0:
        if ex[-1] > n:
            print("NO")
            exit(0)
for i in printing:
    print(i)