백준 1874번: 스택 수열 (Python)

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

---

Level: Silver II

Solved By: Stack

 

이미 기존에 버린 값을 찾는 것은 'NO'를 출력해야 하기 때문에 pop을 통해 버린 값이라면, visited를 통해 체크를 해줍니다.

핵심 아이디어는 이전 값과 지금 값을 비교하면서 2가지로 나누어지는 케이스에 대해 조건을 잘 걸어주면 됩니다.

이전 값(prev)이 현재 값(value) 보다 큰 경우

prev에서 value로 1씩 감소하면서 스택에서 pop을 한 값(== visited가 True)이면, 건너뜁니다.

그리고, 지금은 감소이기 때문에 prev 미만, value 이상의 버리지 않았던 값들은 모두 스택에서 버리는 과정입니다.

그래서 pop을 하지 않은 값들에 대해 pop을 해주면서 Result List에 '-'를 append 시킵니다.

이전 값(prev)이 현재 값(value) 보다 작은 경우

prev에서 value로 1씩 증가하면서 스택에서 pop을 한 값(== visited가 True)이면, 건너뜁니다.

그리고, 지금은 증가이기 때문에 prev 초과, value 이하의 새로운 값들을 스택에 넣는 과정입니다.

그래서 Result List에 '+'를 append 시킵니다.

그리고, value를 다음 수열에 붙여야 되기 때문에 마지막에 value를 pop해주는 코드를 꼭 작성해야 합니다.

초기, 맨 처음 원소

맨 처음 원소에 대해서는 기저 사례로 취급하여 if i == 0에 대해 코드를 작성합니다.

from collections import deque

n = int(input())
li = []
visited = [False for i in range(0, n+1)]

for i in range(n):
    a = int(input())
    li.append(a)

flag = True
res_li = []
st = deque([])

for i, value in enumerate(li):
    if visited[value]:
        flag = False
        break

    if i == 0:
        for j in range(1, value + 1):
            st.append(j)
            res_li.append('+')
        visited[st.pop()] = True
        res_li.append('-')
    else:
        prev = li[i-1]
        if prev > value:
            for j in range(prev, value-1, -1):
                if visited[j] == True:
                    continue
                visited[st.pop()] = True
                res_li.append('-')
        else:
            for j in range(prev, value+1):
                if visited[j] == True:
                    continue
                st.append(j)
                res_li.append('+')
            visited[st.pop()] = True
            res_li.append('-')


if flag == True:
    for v in res_li:
        print(v)
else:
    print('NO')