[BOJ] 스택수열

www.acmicpc.net/problem/1874

1874번: 스택 수열

풀이

• 1 ~ N까지 전체 iteration수행

• 정답을 target에 리스트형태로 저장.

• stack, target을 비교하면서 push, pop연산 수행

• n과 target값과 같으면 stack의 값을 역순으로 다시 확인하면서 push, pop연산 수행.

N = int(input())
target = [int(input()) for i in range(N)]
target_pos = 0

ans = []
stack = []
switch = 0
# 1부터 n까지 전체 iteration
for n in range(1, N+1):
    if n < target[target_pos]:
        stack.append(n)
        ans.append('+')

    elif n == target[target_pos]:
        ans.append('+')
        ans.append('-')
        target_pos += 1

        # 뒤로 돌면서 확인
        stack_back_idx = len(stack)-1
        while stack_back_idx >= 0:

            # 봤는데 target과 같음 -> pop
            if stack[stack_back_idx] == target[target_pos]:
                stack_back_idx -= 1
                target_pos += 1
                stack.pop()
                ans.append('-')

            elif stack[stack_back_idx] < target[target_pos]:
                break

            else:
                switch = 1
                break
    if switch == 1:
        print('NO')
        break

if switch != 1:
    print('\n'.join([i for i in ans]))