백준 - 2493

내가 풀었던 방법 (틀림)

import sys

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


top = list(map(int, sys.stdin.readline().split()))

ans = []

while len(top) != 1:
    cur_tower = top.pop()

    if max(top) < cur_tower:
        ans.append(0)
    else:
        for i in range(len(top) - 1, -1, -1):
            if top[i] >= cur_tower:
                ans.append(i + 1)
                break
ans.append(0)
ans = ans[::-1]
print(ans)

• 난 처음에 뒤에서 부터 tower를 빼주고 빼준뒤 tower list에서 하나씩 검사하며 더 큰게 있을시 answer에 해당 index를 append해주는 방식을 사용함.
• 처음에 4를 pop --> 7이 더 크니 answer에 i + 1인 4를 append
• 근데 시간 초과 오류뜸 ㅅㅅ

정답

import sys

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


top = list(map(int, sys.stdin.readline().split()))

stack = []
ans = [0] * N

for i in range(len(top)):
    while stack:
        if top[stack[-1][0]] > top[i]:
            ans[i] = stack[-1][0] + 1
            break
        else:
            stack.pop()

    stack.append([i, top[i]])

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

• 6 9 5 7 4
• 일단 1번째로 알아야 될께 왼쪽부터 간다고 치면 stack에 (0,6)들어감
• 그다음에 9랑 비교해서 9가 더 높으니 (0,6)은 필요없어짐 --> pop하고 (1,9) 넣음
• 5랑 (1,9) 비교하고 ans 업데이트 및 stack에 (2,5) 넣어줌
• 7이랑 5랑 비교하는데 5가 더 작음. stack pop해주고 9랑 7비교하고 7이 더 작으므로 ans 업데이트 및 stack에 (3,7) 넣어줌
• 이런식으로 진행하면 문제 풀어짐