백준 2493 : 탑 - historyover.com

Python을 이용한 2493번 : 탑에 대해서 포스팅하겠습니다. 2493번은 자료 구조, 스택로 분류되는 문제입니다.

Table of Contents

1. 2493번 문제설명

입력:

첫째 줄에 탑의 수 N (1 ≤ N ≤ 500,000)
둘째 줄에 N개의 탑들의 높이 (1 ≤ 높이 ≤ 100,000,000)

목표:

각 탑에서 발사한 레이저 신호를 수신하는 첫 번째 탑의 인덱스를 찾는 것

출력:

각 탑에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력
만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력

2. 2493번 접근방법

1. 문제 이해하기

문제에서 각 탑은 왼쪽으로 레이저 신호를 발사하며, 가장 먼저 만나는 탑에서만 신호를 수신합니다. 예제 입력을 통해 이해해 보면, 다음과 같습니다:

탑의 높이 순서: 6, 9, 5, 7, 4

탑들은 왼쪽으로 레이저를 발사하여 다음과 같이 신호를 수신합니다:

첫 번째 탑(6): 수신 없음
두 번째 탑(9): 수신 없음
세 번째 탑(5): 두 번째 탑(9)이 수신
네 번째 탑(7): 두 번째 탑(9)이 수신
다섯 번째 탑(4): 네 번째 탑(7)이 수신

이 문제를 해결하기 위해선 각 탑의 레이저 신호를 어느 탑이 수신하는지 찾아야 합니다.

2. 효율적인 해결 방법 찾기

탑의 수가 최대 500,000개일 수 있으므로, 모든 쌍을 비교하는 O(N^2) 시간 복잡도는 너무 비효율적입니다. 대신 더 효율적인 방법을 찾아야 합니다. 각 탑이 자신보다 높은 탑을 찾는 문제이므로, 적절한 자료구조를 사용하여 이 과정을 최적화할 필요가 있습니다.

3. 자료구조 선택: 스택

스택은 LIFO(Last In First Out) 구조를 가지며, 최근 삽입된 요소를 빠르게 제거할 수 있습니다. 이 문제에서는 다음과 같은 이유로 스택을 사용하여 효율적으로 해결할 수 있습니다:

스택을 사용하면 현재 탑보다 높은 탑이 나타날 때까지 이전 탑을 제거할 수 있습니다.
현재 탑이 이전 탑들보다 낮으면, 현재 탑의 레이저 신호를 수신하는 탑은 스택의 맨 위에 있는 탑이 됩니다.

4. 스택 방식을 적용한 구체적 사고 과정

각 탑을 순서대로 순회합니다.
스택을 사용하여 현재 탑보다 낮은 탑을 제거합니다.
스택이 비어있지 않으면, 스택의 맨 위에 있는 탑이 현재 탑의 레이저 신호를 수신합니다.
현재 탑의 인덱스를 스택에 추가합니다.
결과를 출력합니다.

3. 2493번 구현

3-1. 2493번 코드

Python

import sys
input = sys.stdin.readline

# 탑의 수를 입력받습니다.
n = int(input())
# 각 탑의 높이를 입력받아 리스트로 저장합니다.
nums = list(map(int, input().split()))
# 각 탑의 레이저 신호가 수신되는 탑의 인덱스를 저장할 결과 리스트를 초기화합니다.
result = [0 for i in range(n)]
# 스택을 초기화합니다. 스택에는 탑의 인덱스를 저장합니다.
stack = []

# 모든 탑을 순회합니다.
for i in range(n):
    # 현재 탑(i번째 탑)보다 낮은 탑이 스택에 있으면, 이는 현재 탑에 의해 레이저 신호를 수신할 수 없으므로 스택에서 제거합니다.
    while stack and nums[stack[-1]] < nums[i]:
        stack.pop()
    # 스택이 비어있지 않다면, 스택의 마지막 요소(가장 오른쪽에 있으면서 현재 탑보다 높거나 같은 탑)는 현재 탑의 레이저 신호를 수신할 수 있습니다.
    if stack:
        # 결과 리스트에 수신 탑의 인덱스를 저장합니다. 인덱스는 1부터 시작하므로 1을 더합니다.
        result[i] = stack[-1] + 1
    # 현재 탑의 인덱스를 스택에 추가합니다.
    stack.append(i)

# 결과 리스트를 공백으로 구분하여 문자열로 변환한 후 출력합니다.
print(" ".join(map(str, result)))