[백준]2493번_탑

문제 링크 : https://www.acmicpc.net/problem/2493

2493번: 탑

처음에 그냥 무턱대고 푼 코드 (시간초과)

n = int(input())
towers = list(map(int,input().split()))
answer = []
for idx, tower in enumerate(towers):
    if idx == 0:
        answer.append(0)
        continue
    else:
        while idx>=0:
            if tower < towers[idx-1]:
                answer.append(idx)
                break
            else:
                idx -= 1
        if idx < 0 :
            answer.append(0)

for ans in answer:
    print(ans, end=" ")

리스트 만든 것에서 인덱스 하나씩 줄여가며 했더니 시간초과 나왔다.

 

다시 스택을 활용하여 짰더니 통과되었다.

n = int(input())
towers = list(map(int,input().split()))
stack = []

for idx, tower in enumerate(towers):
    while stack :
        if stack[-1][1] > tower:
            print(stack[-1][0],end=" ")
            break
        stack.pop()
    if not stack:
        print(0,end=" ")
    stack.append([idx+1,tower])