[정글 알고리즘] - [중] - 백준2493 탑

처음엔 오른쪽부터 접근했다가 시간 초과가 났다고 들었다. 왜 왼쪽부터 해야 자연스러운지, 스택이 어떻게 O(N)을 만드는지 따라가 봤다.

---

 

N개의 탑이 왼쪽부터 순서대로 서 있다. 각 탑은 레이저 신호를 왼쪽으로 쏜다.
신호는 자기보다 높은 탑을 처음 만나면 그 탑에 수신된다. 각 탑의 신호를 수신한 탑 번호를 출력한다. 아무도 없으면 0.

항목	내용
문제 번호	백준 2493
난이도	골드 5
분류	자료구조, 스택
입력 범위	N ≤ 500,000
핵심 연산	각 탑에서 왼쪽으로 처음 만나는 더 큰 탑 번호 출력

예제

탑 번호	1	2	3	4	5
높이	6	9	5	7	4
출력 (수신 탑)	0	0	2	2	4

---

왜 단순하게 짜면 O(N²)인가

각 탑마다 왼쪽을 처음부터 다시 탐색하면 이렇게 된다.

# 단순 O(N²) 풀이 — 시간 초과
for i in range(n):
    for j in range(i-1, -1, -1):   # 매번 왼쪽 전체 탐색
        if heights[j] > heights[i]:
            answer[i] = j + 1
            break

↑ N = 500,000에서 최악의 경우 약 1,250억 번 비교 → 시간 초과

높이가 오름차순(1 2 3 4 5)으로 주어지면 마지막 탑은 왼쪽 전체를 다 뒤져야 한다. 이런 케이스에서 O(N²)가 그대로 터진다.

---

스택으로 O(N) 만드는 아이디어

왼쪽에서 오른쪽으로 진행하면서 스택에 (탑 번호, 높이)를 담는다. 스택에는 "아직 누군가의 수신탑이 될 가능성이 있는 탑"만 남긴다.

현재 탑 높이를 h라고 할 때, 스택 맨 위 탑의 높이가 h보다 작으면 그 탑은 앞으로도 영원히 수신탑이 될 수 없다. 현재 탑이 더 크기 때문에, 오른쪽에서 오는 탑 입장에서도 그 작은 탑은 현재 탑에 가려진다. 그러므로 바로 pop한다.

이 논리로 각 탑은 스택에 정확히 한 번 들어가고 한 번 나온다. 전체 push/pop 횟수 합계가 O(N)이다.

상황	처리	이유
스택 top 높이 < 현재 높이	pop — 반복	이 탑은 앞으로 쓸모없음
스택 top 높이 > 현재 높이	스택 top 번호를 답으로	왼쪽에서 처음 만나는 더 큰 탑
스택이 비어 있음	답 = 0	왼쪽에 더 큰 탑 없음
처리 후	현재 탑을 스택에 push	이후 오른쪽 탑들의 후보가 됨

---

코드

import sys

n = int(sys.stdin.readline())
heights = list(map(int, sys.stdin.readline().split()))

stack = []    # (탑 번호, 높이)
answer = []

for i in range(n):
    current_height = heights[i]

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

    if stack:
        answer.append(stack[-1][0])
    else:
        answer.append(0)

    stack.append((i + 1, current_height))

print(*answer)

문법 — stack[-1][1]이 뭔가

스택에는 (탑 번호, 높이) 형태의 튜플이 들어있다.

stack = [(1,6), (2,9), (3,5)]

stack[-1]      # (3, 5)    ← 맨 위 원소 (튜플 전체)
stack[-1][0]   # 3         ← 탑 번호
stack[-1][1]   # 5         ← 탑 높이

표현	의미	용도
stack[-1]	스택 맨 위 원소 (튜플)	전체 참조
stack[-1][0]	탑 번호	답에 저장할 때
stack[-1][1]	탑 높이	높이 비교할 때

while 루프가 바로 옆만 보는 게 아닌 이유

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

while이기 때문에 조건이 맞는 한 계속 반복된다. 바로 옆 탑이 안 되면 그 왼쪽, 또 그 왼쪽까지 pop하면서 진행한다.

높이 예시	5번 탑(높이 12) 처리 과정
10 3 7 4 12	4 작음→pop, 7 작음→pop, 10 작음→pop, 스택 빔→답 0
10 3 7 4 9	4 작음→pop, 7 작음→pop, 10 큼→멈춤, 답 1(1번 탑)
6 4 8	4 작음→pop, 6 작음→pop, 스택 빔→답 0

---

동작 시뮬레이션 — 높이: 6 9 5 7 4

탑	높이	while 처리	답	push 후 스택
1번	6	스택 비었음	0	[(1,6)]
2번	9	(1,6) 6<9 → pop / 스택 빔	0	[(2,9)]
3번	5	(2,9) 9>5 → 멈춤	2	[(2,9),(3,5)]
4번	7	(3,5) 5<7 → pop / (2,9) 9>7 → 멈춤	2	[(2,9),(4,7)]
5번	4	(4,7) 7>4 → 멈춤	4	[(2,9),(4,7),(5,4)]
최종 출력			0 0 2 2 4

3번 탑(높이 5)의 왼쪽에는 6, 9가 있다. 바로 옆 2번 탑(9)이 더 크니까 while이 첫 번 만에 멈추고 2번이 답이 된다.
4번 탑(높이 7)은 바로 왼쪽인 3번 탑(5)이 더 작아서 pop하고, 그다음 2번 탑(9)에서 멈춘다.

---

왜 왼쪽→오른쪽인가

문제는 각 탑의 왼쪽에서 처음 만나는 더 큰 탑을 찾는 것이다.
왼쪽에서 오른쪽으로 진행하면, 현재 탑을 처리할 때 왼쪽 정보가 이미 스택에 쌓여 있다.

진행 방향	현재 탑에서 하는 일	구현 난이도
왼쪽 → 오른쪽	현재 탑의 답을 지금 바로 구한다	✅ 직관적
오른쪽 → 왼쪽	현재 탑이 나중에 누구 답이 되는지 관리한다	⚠️ 사고방식이 바뀌어 구현이 꼬임

오른쪽에서 왼쪽으로 가면, 각 탑에서 왼쪽을 다시 탐색하는 패턴이 나오기 쉽다. 높이가 오름차순이면 거의 모든 탑이 왼쪽 전체를 뒤져야 해서 O(N²)이 된다.

# 오른쪽부터 → 쉽게 O(N²) 패턴이 나온다
높이: 1 2 3 4 5 6 7 8

8 → 왼쪽 7개 다 확인
7 → 왼쪽 6개 다 확인
...
합계: 약 32번 → N = 500,000이면 약 1,250억 번

↑ 방향 자체의 문제가 아니라, 이 방향으로 짜면 매번 다시 탐색하는 구조가 나오기 쉽다.

---

O(N) 동작 원리

왜 O(N)인지 핵심은 이것이다.

각 탑은 스택에 정확히 한 번 들어가고 (push), 최대 한 번 나온다 (pop).
N개의 탑에 대해 push N번, pop 최대 N번 → 전체 연산 합계가 O(N).

방식	탑 1개당 연산	전체 N개	N=500,000일 때
이중 반복 (O(N²))	최대 N번 탐색	O(N²)	~2,500억 번
스택 (O(N))	push 1회 + pop 최대 1회	O(N)	~100만 번

---

시간복잡도 정리

단계	연산	복잡도	근거
순회	for i in range(n)	O(N)	N개 탑 1회 순회
push	stack.append()	O(N) 합계	각 탑 최대 1회 push
pop	stack.pop()	O(N) 합계	각 탑 최대 1회 pop
전체	—	O(N)	—

---

최종 코드

# 스택 — 탑 (백준 2493)
# https://www.acmicpc.net/problem/2493
import sys

n = int(sys.stdin.readline())
heights = list(map(int, sys.stdin.readline().split()))

stack = []    # (탑 번호, 높이)
answer = []

for i in range(n):
    current_height = heights[i]

    # 나보다 작은 탑은 앞으로 쓸모없으니 제거
    while stack and stack[-1][1] < current_height:
        stack.pop()

    # 스택에 남은 탑 중 가장 가까운(맨 위) 탑이 수신탑
    if stack:
        answer.append(stack[-1][0])
    else:
        answer.append(0)

    # 현재 탑을 이후 오른쪽 탑들의 후보로 등록
    stack.append((i + 1, current_height))

print(*answer)

---

이 문제에서 스택을 쓰는 이유가 명확했다. 현재 탑이 왼쪽 탑들 중 작은 것들을 영구적으로 지울 수 있기 때문에, 반복 탐색 없이 O(N)이 가능하다. 오른쪽부터 접근했다가 시간 초과가 나는 것도 구조적인 이유가 있었다.

🌿