BAEKJOON #1874) 스택수열

문제 유형: 스택, 그리디

이 문제는 문제에서 요구하는대로 구현만 해도 풀 수 있다...는데,,, 나는 1시간 잡아도 못 풀어서 결국 나동빈 강사님의 해설 강의를 보고 풀었다..,,ㅎㅠㅠㅠㅠㅠ

어려워어려워어려워

그대로 구현하라는데 그게 어려워,,,ㅠㅠㅠㅠ

공부 진짜 많이 해야할듯쿄쿄

 

문제 풀이 핵심 아이디어는 다음과 같다.

1. 스택에 원소를 삽입할 때는 단순히 특정 수에 도달할 때까지 삽입(push)한다.

2. 스택에서 원소를 연달아 빼낼 때, 내림차순을 유지할 수 있는 확인한다.

 

#코드

n = int(input())

count = 1
stack = []
result =[]

for i in range(1, n+1):
    data = int(input())
    while count <= data:
        stack.append(count)
        count += 1
        result.append('+')
    if stack[-1] == data:
        stack.pop()
        result.append('-')
    else:
        print('NO')
        exit(0)

print('\n'.join(result))

• data를 input으로 받으면서 내가 쌓으려고하는 data 값에 도달할때까지 count를 하나씩 늘려가면서 result에 '+'를 append한다.
• count가 data에 도달해서 while문을 빠져나왔을 때, stack에 쌓인 최상위노드가 내가 쌓으려고 하는 data 값인지 확인하고 맞으면 result에 '-'를 집어 넣고, stack의 최상위 노드를 빼내기(pop()) → Last In Firtst Out
• 최상위 노드가 내가 쌓으려고 하는 data와 같지 않다면 "NO" 프린트하고 프로그램 종료