[Python][백준_2493] 탑

문제

2493번: 탑

풀이과정

처음에는 완전탐색으로 풀었더니 시간초과가 발생했다.

N = int(input())
arr = list(map(int, input().split()))
answer = []
        
for i in range(N):
    answer.append(0)
    for j in range(i-1, -1, -1):
        if arr[i] < arr[j]:
            answer[-1] = j+1
            break

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

< Stack을 사용한 풀이 >

왼쪽 탑의 높이보다 높은 탑들의 [인덱스, 값]을 stack에 넣으면서 수신이 되는 탑이 항상 top에 위치하도록 한다.

1. N 과 arr 를 입력받아 저장한다
2. arr 를 반복하면서 이번에 들어올 숫자보다 작은 숫자를 전부 제거한다
3. stack 이 비어있으면 0을, 비어있지 않으면 stack 의 top의 숫자를 answer 에 저장한다
4. stack 에 [인덱스, 숫자] 를 넣는다
5. arr 를 출력형식에 맞게 출력한다

Code

# 1
N = int(input())
arr = list(map(int, input().split()))
answer = []
stack = []

for (idx, num) in enumerate(arr):
    # 2
    while(stack) and stack[-1][1] < num:
        stack.pop(-1)
    # 3
    if len(stack) == 0:
        answer.append(0)
    else:
        answer.append(stack[-1][0])
    # 4
    stack.append([idx + 1, num])
    
# 5
for a in answer:
    print(a, end=" ")