백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-2493 탑 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/2493

반응형

솔루션 살펴보기!!

import sys

class Pair:
    def __init__(self, x, y):
        self.x = x  # 건물의 높이
        self.y = y  # 건물의 위치

def main():
    input = sys.stdin.read
    data = list(map(int, input().split()))  # 입력을 한번에 처리하고 정수 리스트로 변환

    N = data[0]
    heights = data[1:]
    
    receive = [0] * (N + 1)  # 수신받는 건물 위치 저장 (인덱스 1부터 N까지 사용)
    stack = []  # 스택을 리스트로 처리

    # 첫 번째 건물 처리
    stack.append(Pair(heights[0], 1))
    
    # 2번째 건물부터 처리
    for i in range(1, N):
        n = heights[i]
        
        while stack:
            # 자신보다 작은 건물들은 스택에서 제거
            if stack[-1].x < n:
                stack.pop()
            # 자신보다 큰 건물이 있으면 해당 건물의 위치를 저장하고 종료
            else:
                receive[i + 1] = stack[-1].y
                break
        
        # 현재 건물을 스택에 추가
        stack.append(Pair(n, i + 1))

    # 결과 출력 (1번 건물부터 N번 건물까지 수신받는 건물 위치 출력)
    print(" ".join(map(str, receive[1:N+1])))

if __name__ == "__main__":
    main()

코드 흐름 및 주요 개념 정리 

이 Python 코드는 특정 건물의 높이를 기준으로, 각 건물이 왼쪽에 있는 건물 중 자신보다 높은 건물에서 신호를 받는 문제를 해결합니다. 코드는 스택을 활용한 알고리즘으로, 각 건물에 대해 자신보다 앞서 있는 건물들과 비교하며 가장 가까운 자신보다 높은 건물을 찾는 방식입니다.

코드 흐름 설명

입력 처리

input = sys.stdin.read
data = list(map(int, input().split()))
N = data[0]
heights = data[1:]

 

• 먼저, sys.stdin.read를 사용해 전체 입력을 한 번에 처리합니다.
• data는 map 함수를 사용해 정수로 변환된 리스트입니다. 첫 번째 요소는 건물의 개수 N이고, 그 이후의 값들은 각 건물의 높이를 나타냅니다.

기본 설정

receive = [0] * (N + 1)
stack = []

 

 

• receive 리스트는 각 건물이 신호를 받는 다른 건물의 위치를 저장합니다. 건물 번호가 1부터 시작하기 때문에, 인덱스 1부터 N까지 사용할 수 있도록 길이를 N+1로 설정했습니다.
• stack은 건물의 높이와 위치를 저장하는 데 사용됩니다. 각 건물은 Pair 클래스를 통해 높이(x)와 위치(y)를 함께 관리합니다.

첫 번째 건물 처리

stack.append(Pair(heights[0], 1))

 

• 첫 번째 건물의 높이와 위치를 스택에 추가합니다. 첫 번째 건물은 앞에 다른 건물이 없으므로 바로 스택에 추가됩니다.

2번째 건물부터 N번째 건물까지 반복 처리

for i in range(1, N):
    n = heights[i]
    
    while stack:
        if stack[-1].x < n:
            stack.pop()
        else:
            receive[i + 1] = stack[-1].y
            break
    
    stack.append(Pair(n, i + 1))

 

• for 루프를 통해 2번째 건물부터 N번째 건물까지 처리합니다.
• 각 건물의 높이를 n으로 설정하고, while stack을 통해 현재 스택에 있는 건물과 높이를 비교합니다.
  • 스택에서 꺼낸 건물의 높이가 현재 건물보다 낮으면, 그 건물은 신호를 보내지 못하므로 스택에서 제거(pop())합니다.
  • 만약 스택의 최상단 건물이 현재 건물보다 높으면, 해당 건물에서 신호를 받는 것으로 처리하고, 그 건물의 위치를 receive[i+1]에 저장한 후 루프를 종료합니다.
• 현재 건물의 높이와 위치는 스택에 추가됩니다. 이는 다음 건물이 처리될 때 다시 비교할 수 있도록 하기 위함입니다.

결과 출력

print(" ".join(map(str, receive[1:N+1])))

 

• receive 리스트에서 건물 번호 1번부터 N번까지 신호를 받은 건물의 위치를 출력합니다. join을 사용해 공백으로 구분된 문자열로 변환하여 출력합니다.

728x90

주요 개념 설명

1. 스택 (Stack)
   • 스택은 LIFO(Last-In, First-Out) 구조를 가지는 자료구조입니다. 즉, 나중에 들어온 데이터가 먼저 나가게 됩니다. 이 문제에서는 스택을 사용해 현재 건물보다 앞에 있는 건물들의 높이를 저장하며, 현재 건물보다 낮은 건물은 스택에서 제거하고, 더 높은 건물만 남기기 위해 사용합니다.
   • 스택의 주요 연산은 append()(push)와 pop()이며, 이를 통해 건물을 비교하면서 처리합니다.
2. 탑의 수신 규칙
   • 각 건물은 자신보다 앞에 있는 건물 중에서 자신보다 높은 건물에게만 신호를 받을 수 있습니다. 즉, 오른쪽에 있는 건물은 왼쪽에 있는 건물과 높이를 비교해 신호를 받을 수 있는지 판단합니다.
   • 앞선 건물 중 자신보다 낮은 건물들은 신호를 받을 수 없으므로, 스택에서 제거됩니다.
3. 효율적인 처리
   • 스택을 사용한 최적화: 이 문제에서 스택을 사용하는 이유는, 반복적으로 모든 건물에 대해 비교하지 않기 위함입니다. 스택을 통해 자신보다 낮은 건물을 제거해 나가면서 현재 건물과 비교하기 때문에, 매번 전체 건물을 비교하지 않고도 효율적으로 문제를 해결할 수 있습니다.
   • 이 방식은 모든 건물에 대해 push와 pop 연산을 한 번씩 수행하게 되어 시간 복잡도는 O(N)입니다. 이는 각 건물에 대해 O(1) 시간 복잡도로 처리할 수 있기 때문에 성능이 매우 효율적입니다.
4. Pair 클래스
   • Pair 클래스는 두 개의 값(높이와 위치)을 하나로 묶어 관리하는 역할을 합니다. 이는 스택에서 각 건물의 높이와 위치를 함께 저장하고 처리하기 위함입니다. Python에서는 튜플이나 간단한 클래스를 사용해 두 개 이상의 값을 함께 다루는 것이 일반적입니다.