[알고리즘][Python] 백준(BOJ) 2493 탑_파이썬

 

2493 탑    www.acmicpc.net/problem/2493

2493번: 탑

 

 

 

 

 

문제 풀기 전 공부할 것 : 자료구조, 스택

 

 

 

 

 

 

 

풀이 1

<내용>

• 탑의 높이를 입력받는다.
• 탑의 높이와 인덱스를 같이 저장한다.
• 탑이 empty가 아니라면 수신할 수 있는 탑을 찾을 때까지 stk에 저장하고 있는다.
• heapq를 이용해 높이가 낮은 탑부터 pop해서 계산을 여러 번 하지 않아도 되게 한다.

 

 

 

<코드>

import heapq

n = int(input())
height = list(map(int, input().split()))
height = [(i+1, j) for i, j in enumerate(height)]
res = [0 for _ in range(n)]
stk = []
while height:
    i, j = height.pop()
    if not height:
        break
        
    if stk and stk[0][0] <= height[-1][1]:
        while stk:
            if stk[0][0] <= height[-1][1]:
                q, p = heapq.heappop(stk)
                res[p-1] = height[-1][0]
            else:
                break
    
    if height[-1][1] >= j:
        res[i-1] = height[-1][0]
    else:
        heapq.heappush(stk, (j, i))
                

print(*res)

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 왼쪽부터 값을 읽으면 더 간단하게 문제를 해결할 수 있다.
• 탑의 높이를 입력받는다.
• 왼쪽의 탑이 현재 탑보다 작다면 오른쪽의 탑에서 수신은 현재 탑만 의미 있다.
• 따라서 현재 탑보다 낮은 왼쪽 탑을 저장하지 않는 방법을 이용한다.

 

 

 

<코드>

n = int(input())
height = list(map(int, input().split()))
stk, res = [], []
for i in range(n):
    while stk:
        if stk[-1][1] < height[i]:
            stk.pop()
        else:
            break
    if stk:
        res.append(stk[-1][0]+1)
    else:
        res.append(0)
        
    stk.append((i, height[i]))
    
print(*res)