스택 수열 (실버 2)

문제 이해가 어려움. 오름차순 push라 1, 5, 7 이렇게 푸시해도 되는 줄 알았지만 생각해보니 1, 5 ,7 push를 하면 나중에 언젠간 2를 푸시해야하는데 그럼 오름차순이 깨짐, 무조건 1,2,3... 순으로 push해야 함.

from sys import stdin

n = int(stdin.readline())
target = []
for i in range(n):
    target.append(int(stdin.readline()))

init = list(range(1, n + 1))

push_item = 1
stack = []
calcul = []
no = False
for t in target:
    while True:
        if len(stack) < 1:
            stack.append(push_item)
            push_item += 1
            calcul.append("+")

        if len(stack) > 0:
            if t == stack[-1]:
                stack.pop()
                calcul.append("-")
                break

        if len(stack) > 0:
            if t > stack[-1]:
                stack.append(push_item)
                push_item += 1
                calcul.append("+")

        if len(stack) > 0:
            if t < stack[-1]:
                no = True
                break

if no:
    print("NO")
else:
    for i in calcul:
        print(i)

탑 (골드 5)

왼쪽 방향이라 헷갈릴 수 있는 문제, 처음부터 예시를 그려가며 생각해보면 왜 스택이 필요한지 느껴짐. 일단 처음에는 들어오는 요소마다 서칭할까 생각했는데 그러기엔 입력에 주어지는 숫자들이 너무 커서 시간복잡도 기준으로 N^2이 나오니 시도조차 안함. N^2이하로 시간복잡도를 처리하기 위해 스택, 큐 등을 고려한 결과 스택으로 새로 들어오는 요소와 마지막 요소를 숫자 크기 비교를 해주면서 처리하면 금방 풀리는 문제

from sys import stdin

n = int(stdin.readline())
tower_lst = list(map(int, stdin.readline().split()))
tower_lst_rev = [x for x in tower_lst[::-1]]
tower_recieve = [0] * n
stack = []
for idx, i in enumerate(tower_lst_rev):
    if idx == 0:
        stack.append((i, idx))
    else:
        while True:
            if len(stack) > 0:
                if i >= stack[-1][0]:
                    pop_item = stack.pop()
                    tower_recieve[pop_item[1]] = idx

                else:
                    stack.append((i,idx))
                    break
            else:
                stack.append((i, idx))
                break

back = [-(x - n) for x in tower_recieve[::-1]]

for i in back:
    if i == n:
        print(0, end=" ")
    else:
        print(i, end=" ")