[#2493] 탑

RookieAND·2022년 7월 7일

백준 스택 코테

BaekJoon

목록 보기

26/42

❓ Question

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

📖 Before Start

스택을 사용하여 더 효율적으로 탐색을 진행해야 하는 문제다.

이번 문제는 스택 자료구조를 사용하여 탐색 과정을 최적화 해야 하는 문제였다.
이 문제 또한 처음에는 완전 탐색으로 접근하였으나, 결국 답안의 도움을 받아야 했다.

✒️ Design Algorithm

송신 가능한 탑이 정확히 어느 위치에 있는지를 파악해야 한다.

N 개의 탑이 일렬로 나열되어 있고, 각 탑은 오른쪽에서 왼쪽으로 통신이 가능하다.
왼쪽으로 신호를 보낼 경우, 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

즉, 현재 탑의 위치를 기준으로 좌측에 위치한 탑들 중에서 높이가 더 높으면서
가장 가까이 위치한 탑이 있다면 수신이 가능하다는 의미고, 아니라면 불가능하다.

따라서 내가 처음으로 세운 문제 풀이 방식은 아래와 같다.

오른쪽에 위치한 탑부터, 현 위치를 기준으로 왼쪽에 위치한 탑의 정보를 읽는다.
만약 왼쪽에 위치한 탑이 현재 탑보다 높이가 높을 경우, 이를 결과에 저장한다.

💻 Making Own Code

❌ Wrong Code

import sys

read = sys.stdin.readline

N = int(read())
towers = list(map(int, read().split()))
result = []

while towers:
    tower = towers.pop()
    if not towers:
        result.append(0)
        break
    # 남은 타워와 송신이 불가능한 경우, 0을 추가함.
    if tower > max(towers):
        result.append(0)
    for i in range(len(towers) - 1, 0, -1):
        if tower <= towers[i]:
            result.append(i + 1)
            break

print(*result[::-1])

역시나 50만개나 되는 자료를 완전 탐색으로 푸는 방식은 잘못되었다.

이 코드를 제출하면서도 시간 초과가 분명히 날 거라는 예상은 했지만, 역시나였다.
그렇다면 탐색을 최소화할 수 있는 조건이 분명히 있다는 이야기인데.. 참 어려웠다.

결국 이 문제도 30분 간의 고민 끝에 다른 분의 풀이를 보면서 이해를 마쳐야 했다.

✅ Correct Code

import sys

read = sys.stdin.readline

N = int(read())
towers = list(map(int, read().split()))
result = [0 for _ in range(N)]

# 의미있는 탑의 정보를 (인덱스, 높이) 로 저장함.
stack = []
for i in range(N):
    # 의미있는 탑을 높이가 낮은 순대로 하나씩 꺼내어 대조함.
    while stack:
        # 스택 안에서 높이가 낮은 탑보다 현재 탑의 높이가 낮다면?
        # 해당 탑은 가장 높이가 낮은 의미있는 탑과의 교신이 가능.
        if towers[i] < stack[-1][1]:
        	# 높이가 더 큰 탑의 인덱스를 받아와, 결과 목록을 갱신시킨다.
            result[i] = stack[-1][0] + 1
            break
        # 그렇지 않을 경우 해당 탑을 제거하고, 그 다음으로 높이가 낮은 탑을 꺼낸다.
        stack.pop()
    # 스택이 비거나 더 이상의 비교가 불가할 경우, 현재 탑의 정보를 추가해야 함.
    stack.append((i, towers[i]))

print(*result)

핵심은 스택에 신호를 수신할 가능성이 있는 탑들에 대한 정보를 저장하는 것이다.

해당 문제는 역으로 좌측에서부터 탑의 정보를 탐색해야 수월하게 풀 수 있었다.
스택에는 신호를 수신할 가능성이 있는 탑의 정보를 (idx, 높이) 형식으로 넣었다.
또한 스택 내의 정보들은 높이에 대한 내림차순으로 정보를 저장시켰다.

만약 스택이 비었다면, i 번째 위치한 탑의 정보를 스택에 추가한다.
만약 스택이 비지 않았다면, 가장 높이가 낮은 탑에 대한 정보를 불러온다.
현재 탑보다 높이가 낮은 탑의 경우 스택 내에서 순차적으로 제거한다.
현재 탑보다 높이가 더 높은 탑이 있다면, 현재 탑의 정보를 스택에 더한다.
그런 후, 현재 위치에서 수신 가능한 탑의 정보를 결과 목록에 추가해준다.

처음에는 풀이가 잘 이해가 가지 않았는데, 그림으로 문제를 풀어보니 곧장 이해가 갔다.

상단의 탑을 왼쪽부터 오른쪽으로 탐색하는 과정은 아래와 같다

첫번째 탑의 신호를 받을 수 있는 탑은 없다. 따라서 스택에 해당 탑의 정보를 추가한다.
- 현재 스택 : [(0, 6)], 결과 목록 : [0]
두번째 탑의 신호를 받을 수 있는 탑을 스택 내부에서 조회한다.
- 스택의 마지막 탑의 높이 6 이 9 보다 작으므로, 이를 스택에서 제거한다.
- 그런 뒤, 스택이 비었으므로 두번째 탑의 정보를 스택에 마저 추가한다.
- 현재 스택 : [(1, 9)], 결과 목록 : [0, 0]
세번째 탑의 신호를 받을 수 있는 탑을 스택 내부에서 조회한다.
- 스택의 마지막 탑의 높이 9 가 5 보다 더 크므로, 결과 목록을 갱신한다.
- 그런 뒤, 스택 후미에 세 번째 탑의 정보를 마저 추가해준다.
- 현재 스택 : [(1, 9), (2, 5)], 결과 목록 : [0, 0, 2]
네번째 탑의 신호를 받을 수 있는 탑을 스택 내부에서 조회한다.
- 스택의 마지막 탑의 높이 5 가 7 보다 작으므로, 이를 스택에서 제거한다.
- 그 뒤에 오는 원소의 높이 9 가 7 보다는 크므로, 결과 목록을 갱신한다.
- 그런 뒤, 스택 후미에 네 번째 탑의 정보를 마저 추가해준다.
- 마지막으로 결과 목록에 송신 가능한 탑의 정보를 갱신한다.
- 현재 스택 : [(1, 9), (3, 7)], 결과 목록 : [0, 0, 2, 2]
마지막 탑의 신호를 받을 수 있는 탑을 스택 내부에서 조회한다.
- 스택의 마지막 원소의 높이 7 이 4보다 크므로, 결과 목록을 갱신한다.
- 그런 뒤, 스택 후미에 마지막 탑의 정보를 마저 추가해준다.
- 현재 스택 : [(1, 9), (3, 7), (4, 4)], 결과 목록 : [0, 0, 2, 2, 4]