자료구조 문제풀이 -(1)

정지현·2023년 2월 14일
0

PS

목록 보기
2/2
  1. 스택수열

문제를 이해하는 데 조금 오래 걸렸다.
스택에 수를 push 할때는 오름차순으로만 할 수 있는데, 예제 입력 1을 보면 N=8, 43687521 이 들어왔을 때
처음에 4를 pop하기 위해서는 스택에 1234를 push 한 다음 4를 pop해야 하기 때문이다.
이 때, stack의 top이 입력한 숫자보다 클 경우 다른 숫자들을 pop 해야하기 때문에 해당 수열을 만들 수 없게 된다.

n = int(input())
stack = []
answer = []
flag = 0
cur = 1
for i in range(n):
    num = int(input())
    while cur <= num:       # 입력한 수를 만날 때 까지 오름차순으로 push
        stack.append(cur)
        answer.append("+")
        cur += 1

    if stack[-1] == num:    # stack의 TOP이 입력한 숫자와 같다면
        stack.pop()         # 스택의 TOP을 꺼내 수열을 만들어 준다.
        answer.append("-")
    else:                   # stack의 TOP이 입력한 수가 아니면 주어진 스택을 만들 수 없다.
        print("NO")         # 왜냐하면 12345 처럼 오름차순으로 스택이 입력되는데
        exit()

for i in answer:
    print(i)

0개의 댓글