Study/알고리즘

[백준]2493번_탑

혤리 2020. 1. 13. 21:35

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

 

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

www.acmicpc.net

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

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])