[백준 #2493] 탑

1. 문제 설명

2. 해설

처음에 O(n^2)의 시간복잡도로 풀었다가 시간 초과가 나서 어떻게 하면 시간복잡도를 줄일 수 있을까 고민해보았다.

1. 우선 탑을 왼쪽부터 검사하여 인덱스, 값을 쌍으로 묶어 스택에 삽입한다.
2. idx가 1일 때부터, 스택이 빌 때 까지 스택의 최상단 val과 비교하여 스택 쪽이 더 크면 결과 배열에 스택의 최상단 값을 삽입하고, 아닐 경우에는 스택에서 pop()을 해준다.
3. while문이 끝나면 현재 인덱스와 값을 쌍으로 묶어 스택에 넣어준다.

설명이 더 어려우니 코드를 읽어보길 바란다... 나 설명 진짜 못하네

3. 코드

import sys
input = sys.stdin.readline

N = int(input())
tower = list(map(int, input().split()))
stack = []
res = [0] * N

for idx, val in enumerate(tower):
    if idx == 0:
        stack.append([idx, val])
        continue
    else:
        while stack:
            if val < stack[-1][1]:
                res[idx] = stack[-1][0] + 1
                break
            else:
                stack.pop()
        stack.append([idx, val])

print(" ".join(map(str, res)))