[백준 2493] 탑

[BanApp]

import sys

n = int(sys.stdin.readline())

arr = list(map(int,sys.stdin.readline().split()))
ans = [0 for _ in range(n)]
tmp = [[arr.pop(),len(arr)+1]]

while len(arr) > 0:
    t = arr.pop()

    if t >= tmp[0][0]:
        for i in range(len(tmp)):
            ans[tmp[len(tmp) - i - 1][1] - 1] = len(arr) + 1
        tmp = []
        tmp.append([t, len(arr) + 1])

    elif t >= tmp[-1][0]:
        x = tmp.copy()
        for i in range(len(x)):
            if t >= x[len(x) - i - 1][0]:
                ans[x[len(x) - i - 1][1] - 1] = len(arr) + 1
                tmp.pop()
            else:
                break
        tmp.append([t, len(arr) + 1])

    else:
        tmp.append([t, len(arr) + 1])

print(*ans)

간단해보여서 만만하게 봤다가 생각보다 신경쓸게 많았던 문제다.
일단 당연히 이중반복문으로 하는게 제일 간단하지만 O(N^2) 이라서 무조건 시간초과가 난다.
따라서 입력받은 리스트에서 하나씩 꺼내서 tmp에 넣어주면서 비교해준다.
t가 tmp[0]에 있는 원소보다 크면 tmp안에 있는 원소들은 전부 t보다 작다.
만약에 tmp[0] 보다는 크지 않더라도 바로 직전에 tmp에 삽입된 원소보다 t가 크다면 tmp를 전체탐색 해준다.
그 외에는 tmp에 원소 삽입. tmp에 삽입할때 원소값과 위치 값을 같이 삽입해준다.
while문을 한번 돌고 나서 최종적으로 ans를 출력해주면 정답!
문제는 간단하지만 시간초과를 피하기 위해서 복잡해지는 문제다.