백준 2493번 - 탑

탑 문제 바로 가기

풀이 날짜: 2026-03-16

baekjoon 알고리즘 문제 풀이

풀이 코드


n = int(input())
top = list(map(int, input().split()))

answer = [0] * n
stack = []

for i in range(n):
        while stack and stack[-1][1] < top[i]:
            stack.pop()

        if stack:
            answer[i] = stack[-1][0] + 1
        else:
            answer[i] = 0

        stack.append((i,top[i]))
print(*answer)

접근 방법

이 문제는 각 탑이 왼쪽으로 레이저를 발사할 때 처음 만나는 더 높은 탑의 번호를 구하는 문제이다. 단순하게 생각하면 각 탑마다 왼쪽으로 하나씩 비교하면서 높은 탑을 찾을 수 있다. 하지만 탑의 개수가 최대 500,000개이기 때문에 매번 왼쪽을 탐색하면 시간 초과가 발생한다. 따라서 모든 탑을 매번 비교하지 않고 필요한 탑만 남기면서 탐색하는 방법이 필요하다.

핵심 아이디어

현재 탑보다 작은 탑들은 앞으로도 절대 정답이 될 수 없다는 점을 이용했다. 이 특징 때문에 현재 탑보다 작은 탑들은 스택에서 제거해도 된다. 이렇게 하면 스택에는 항상 현재 탑보다 높은 탑들만 남게 되는 것이다.

스택을 사용하는 이유

이 문제에서는 왼쪽 탑들 중에서 가장 가까운 높은 탑을 찾아야 한다.

현재 탑보다 작은 탑들은 스택에서 제거한다.
제거가 끝난 뒤 스택이 비어있지 않다면, 스택 맨 위 탑이 가장 높은 탑이 된다.
그 탑의 번호를 정답 배열에 저장한다.
현재 탑을 스택에 추가한다.

스택에 저장하는 값

(탑의 인덱스, 탑의 높이) 예를 들어 (2, 9)는 3번째 탑이고 높이가 9라는 의미이다. 이렇게 인덱스와 높이를 함께 저장하는 이유는, 나중에 정답으로 탑 번호를 기록해야 하기 때문이다.

정답을 저장하는 방식

정답 배열 answer[i]는 i번째 탑의 레이저를 받는 탑 번호를 의미한다.

스택이 비어 있으면 왼쪽에 더 높은 탑이 없다는 의미이므로 0
스택이 남아 있으면 스택 맨 위 탑이 가장 가까운 높은 탑이므로 그 탑의 번호를 기록

스택에는 (인덱스, 높이) 형태로 저장되어 있기 때문에 탑 번호를 구할 때는 stack[-1][0] + 1을 사용한다.

Vienna sausage