[1874] 스택 수열

해당 문제는 1~10까지 오름차순으로 값을 스택에 push하는 규칙을 갖는다

입력받은 수열을 위 규칙 내에서 스택의 특징인 LIFO(후입선출)로 나열할 수 있는지를 묻는다

list = []
stack = []
result = []
next = 0

N = int(input(""))

for i in range(N):
    list.append(int(input("")))
    if next < list[i]:
        for j in range(list[i]-next):
            result.append("+")
            next += 1
            stack.append(next)
        result.append("-")
        stack.pop()
    elif len(stack) == 0 or (stack[-1] < list[i] and list[i] < next):
        print("NO")
        break
    elif list[i] <= stack[-1]:
        while(True):
            result.append("-")
            if stack.pop() == list[i]:
                break
    if i == N-1:
        for j in result:
            print(j)

 

list는 입력받은 데이터, stack은 수열을 만들 때 사용하는 리스트, next는 스택에 오름차순으로 들어가는 1~10의 지점을 가르키는 포인터로 설정

 

• 현 오름차순의 지점을 가리키는 next보다 입력 수열 list[i]값이 더 클 경우 그 차만큼 반복하여 스택에 push
• 현재 스택의 마지막값보다 list[i]가 크며 next보다 list[i]가 작은 경우 next값을 증가시켜 push를 할 수도, 현재 스택에 담겨있는 값을 pop 할수도 없기 때문에 해당 수열은 만들어질 수 없다
• list[i]가 스택의 마지막 값보다 작거나 같은 경우 스택에는 오름차순으로 값이 들어가있기 때문에 해당 값이 나올때까지 반복하여 pop한다