[백준] 2493번 - 탑

1. 문제 요약

https://www.acmicpc.net/problem/2493

 

각 탑은 왼쪽 방향으로 신호를 보낸다.
이때 자신보다 높은 탑 중에서 가장 가까운 탑이 신호를 받는다.

→  각 탑마다 “왼쪽에서 가장 가까운 높은 탑의 위치”를 구하는 문제

---

2. 처음 접근 (완전탐색)

처음에는 단순하게 생각했다.

“각 탑마다 왼쪽을 쭉 탐색하면서 처음 만나는 큰 탑 찾으면 되겠네?”

그래서 구현한 코드는 다음과 같다.

import sys
input = sys.stdin.readline

n = int(input())
top = list(map(int, input().split()))
answer = [0] * n

for where in range(n - 1, -1, -1):
    height = top[where]
    for index in range(where - 1, -1, -1):
        if top[index] >= height:
            answer[where] = index + 1
            break

print(*answer)

---

3. 문제점

이 방식은 시간복잡도 O(n²) 이다.

• 각 탑마다 왼쪽을 다시 탐색
• 최악의 경우 거의 전체를 매번 탐색

→  입력이 커지면 바로 시간초과

---

고민 포인트

여기서 의문이 들었다.

“이미 한 번 본 탑을 또 다시 보는 게 비효율적인데…
이걸 줄일 방법이 없을까?”

---

4. 핵심 아이디어 (단조 스택)

핵심은 하나였다.

→ “쓸모 없는 탑을 미리 제거하자”

어떤 탑이 쓸모 없을까?

→  현재 탑보다 작은 탑

이유:

• 현재 탑보다 작으면
• 앞으로 등장하는 어떤 탑에게도
• 더 큰 탑보다 먼저 선택될 일이 없음

→  즉, 미래에도 절대 정답이 될 수 없음

---

5. 개선된 풀이

import sys
input = sys.stdin.readline

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

    stack.append((i, top[i]))

print(*answer)

---

6. 동작 원리

 1) 작은 탑 제거

while stack and stack[-1][1] < top[i]:
    stack.pop()

•  현재 탑보다 작은 탑은 전부 제거
• 이유: 앞으로도 절대 필요 없음

---

 2) 정답 찾기

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

• 스택에는 “나보다 큰 탑들만 남아 있음”
•  그 중 가장 가까운 건 stack의 top

---

 3) 현재 탑 추가

stack.append((i, top[i]))

→  이후 탑들을 위한 후보로 저장

---

7. 시간복잡도 비교

방식시간복잡도

완전탐색	O(n²)
단조 스택	O(n)

→   각 원소는 최대 1번 push / 1번 pop