백준 알고리즘 - 탑 (2493번) [Python]

 

 

 문제

 

www.acmicpc.net/problem/2493

2493번: 탑

 

 

 

 

 

 

 문제 상황

 

- 탑의 높이가 주어지고 각 탑이 발사한 레이저 신호는 해당 탑의 왼쪽에 존재하는 탑들 중 더 높고, 가장 가까운 탑에서 수신 가능하다. 각 탑이 발사한 신호를 수신하는 탑의 순서를 반환하여 출력한다.

 

 

 

 

 

 

 

 해결 전략

 

- 단순히 생각하면 하나의 기준 탑을 잡고, 그 왼쪽을 순회하며 봐야하므로 O(N^2)으로 해결 가능하다. 하지만 문제 조건이 최대 500,000개의 탑 이므로 N^2, 혹은 N*M의 순회는 최대 250억 번의 연산을 해야한다. 이를 

O(N)으로 해결해야하며, Stack을 사용한다.

 

 

 

 

 

 

 코드

 

import sys
 
input = sys.stdin.readline
n = int(input())
tower_list = list(map(int, input().split()))
stack = []
result = [0] * n
for i in range(n):
    tower = tower_list[i]
    while stack and tower_list[stack[-1]] < tower:
        stack.pop()
    if stack:
        result[i] = stack[-1] + 1
    stack.append(i)
print(' '.join(map(str, result)))
 

 

 

 

 

 

 

 

 

 해설

 

- 여기서 stack의 의미는 수신이 가능한 탑이다. 10번째 줄의 while문의 의미는 어차피 i번째 타워보다 낮은 타워는 i+1번째 이상의 타워들에서 의미가 없기 때문에 비교에서 제거한다. 즉, 어차피 (i+α)번째 tower가 i번째 tower보다 낮을 경우 최소 i번째 tower에서 수신을 하기 때문에 (i-α)번째 tower는 비교를 위한 stack에 존재할 이유가 없다. 12번째 줄 if stack의 경우, 만약 i번째 tower 왼쪽에 수신 가능한 더 높은 tower가 있다면 반드시 stack안에 존재하므로 stack 마지막 값을 위치로 지정해준다. 마지막에는 해당 타워를 비교 대상에 넣어준다. 

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 조건에 왼쪽에 있는 요소 중 가장 오른쪽에서 수신하므로 꼭 for문으로 돌릴 필요가 없었다. 속도가 크게 차이나는 방법으로, 완전한 괄호 문제처럼 2차원 순회에서 추가적으로 비교 대상을 관찰해야할 조건이 붙는다면 stack을 고려해볼 필요가 있다.