[리트코드] 1840 - Maximum Building Height

1840. Maximum Building Height

Hard

---

You want to build n new buildings in a city. The new buildings will be built in a line and are labeled from 1 to n.

However, there are city restrictions on the heights of the new buildings:

• The height of each building must be a non-negative integer.
• The height of the first building must be 0.
• The height difference between any two adjacent buildings cannot exceed 1.

Additionally, there are city restrictions on the maximum height of specific buildings. These restrictions are given as a 2D integer array restrictions where restrictions[i] = [idi, maxHeighti] indicates that building idi must have a height less than or equal to maxHeighti.

It is guaranteed that each building will appear at most once in restrictions, and building 1 will not be in restrictions.

Return the maximum possible height of the tallest building.

 

Example 1:

Input: n = 5, restrictions = [[2,1],[4,1]]
Output: 2
Explanation: The green area in the image indicates the maximum allowed height for each building.
We can build the buildings with heights [0,1,2,1,2], and the tallest building has a height of 2.

Example 2:

Input: n = 6, restrictions = []
Output: 5
Explanation: The green area in the image indicates the maximum allowed height for each building.
We can build the buildings with heights [0,1,2,3,4,5], and the tallest building has a height of 5.

Example 3:

Input: n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
Output: 5
Explanation: The green area in the image indicates the maximum allowed height for each building.
We can build the buildings with heights [0,1,2,3,3,4,4,5,4,3], and the tallest building has a height of 5.

 

Constraints:

• 2 <= n <= 109
• 0 <= restrictions.length <= min(n - 1, 105)
• 2 <= idi <= n
• idi is unique.
• 0 <= maxHeighti <= 109

---

문제 풀이

문제 분석

이 문제는 일렬로 늘어선 n개의 건물 높이를 결정하는 문제입니다.
제약 조건은 다음과 같습니다.

• 건물 높이는 0 이상의 정수입니다.
• 첫 번째 건물(1번)의 높이는 반드시 0입니다.
• 인접한 건물 간의 높이 차이는 최대 1입니다.
• 특정 건물들에 대해 최대 높이 제한(restrictions)이 주어집니다.

입력: 건물 수 n, 제한 사항 배열 restrictions (각 원소는 [건물번호, 최대높이])
출력: 모든 제약 조건을 만족하면서 가능한 가장 높은 건물의 최대 높이

---

접근 방법

이 문제는 **제약 조건 전파(Constraint Propagation)**와 두 지점 사이의 최대 봉우리 계산을 핵심 아이디어로 사용합니다.

1. 제약 조건 정렬 및 보완: 제한 사항을 건물 번호 순으로 정렬하고, 1번 건물(높이 0)과 n번 건물(이론상 최대 높이 n-1)을 제한 목록에 추가하여 전체 구간을 커버합니다.
2. 양방향 전파(Forward & Backward Pass):
   • 좌→우(Forward): 왼쪽 건물의 제한 높이를 바탕으로 오른쪽 건물의 실질적 최대 높이를 갱신합니다. (왼쪽에서 오른쪽으로 갈 때 높이는 최대 1씩만 오를 수 있음)
   • 우→좌(Backward): 오른쪽 건물의 제한 높이를 바탕으로 왼쪽 건물의 실질적 최대 높이를 갱신합니다. (오른쪽에서 왼쪽으로 갈 때 높이는 최대 1씩만 오를 수 있음)
   • 이 두 과정을 거치면 모든 제한 지점의 높이는 양쪽 제약을 모두 만족하는 최종 확정 최대 높이가 됩니다.
3. 구간 내 최대 높이 계산: 인접한 두 제한 지점 (id1, h1), (id2, h2) 사이에서는 높이가 1씩 변하므로, 두 점을 연결하는 산 모양에서 가장 높은 봉우리의 높이는 (거리 + h1 + h2) // 2 공식을 통해 구할 수 있습니다. 모든 구간에 대해 이 값을 계산하여 최댓값을 찾습니다.

자료구조로는 정렬된 리스트를 사용하며, n이 최대 10^9까지 커질 수 있지만 제한 개수는 최대 10^5이므로 제한 지점만 다루는 희소 배열(Sparse Array) 방식으로 해결합니다.

---

구현 설명

1단계: 제한 사항 정렬 및 경계 추가

• restrictions에 시작점 [1, 0]을 추가하고 건물 번호(id) 기준 오름차순 정렬합니다.
• 마지막 건물 n이 제한 목록에 없으면 [n, n-1]을 추가합니다. (1번이 0이고 최대 1씩 오를 때 n번의 이론적 최대 높이는 n-1)

2단계: 왼쪽에서 오른쪽으로 제약 전파 (Forward Pass)

• 정렬된 제한 리스트를 순회하며 i-1번째 건물의 확정 높이 h1을 이용해 i번째 건물의 높이를 갱신합니다.
• 공식: h2 = min(기존 h2, h1 + (id2 - id1))
• 의미: id1에서 id2까지 최대 1씩 오를 수 있으므로, h1 + 거리를 넘을 수 없습니다. 기존 제한(h2)과 이 도달 가능 높이 중 작은 값이 새로운 확정 높이가 됩니다.

3단계: 오른쪽에서 왼쪽으로 제약 전파 (Backward Pass)

• 리스트를 역순으로 순회하며 i+1번째 건물의 확정 높이 h2를 이용해 i번째 건물의 높이를 갱신합니다.
• 공식: h1 = min(기존 h1, h2 + (id2 - id1))
• 의미: id2에서 id1로 거꾸로 올 때도 최대 1씩만 오를 수 있으므로(즉, id1에서 id2로 갈 때 최대 1씩 내릴 수 있음), h2 + 거리를 넘을 수 없습니다. Forward Pass 결과와 이 값을 비교해 최소값을 취하면 양쪽 제약을 모두 만족하는 최종 확정 높이가 결정됩니다.

4단계: 인접 제한 구간 내 최대 높이 계산

• 확정된 인접 제한 지점 쌍 (id1, h1), (id2, h2) 사이를 봅니다.
• 두 지점을 높이 1씩 변하며 연결할 때 가장 높은 봉우리는 두 경사면이 만나는 지점입니다.
• 공식: peak = (id2 - id1 + h1 + h2) // 2
  • 유도: h1 + x = h2 + (d - x) → 2x = d + h2 - h1 → 최대 높이 = h1 + x = (d + h1 + h2) / 2 (여기서 d = id2 - id1)
• 모든 구간에 대해 이 봉우리 높이를 계산하고 최댓값을 answer에 저장합니다.

---

⏱복잡도 분석

• 시간 복잡도: O(m log m)

  • m은 restrictions의 길이 (최대 10^5).
  • 정렬에 O(m log m), 전파 및 계산에 O(m)이 소요됩니다. n(최대 10^9)과 무관하게 제한 개수에만 의존합니다.

• 공간 복잡도: O(m)

  • 정렬된 제한 리스트를 저장하는 데 O(m) 공간을 사용합니다. 입력 리스트를 직접 수정(in-place)하므로 추가 공간은 상수 수준입니다.

---

핵심 포인트

1. 희소 제약 조건 처리: n이 매우 크므로(10^9) 모든 건물을 순회할 수 없습니다. 제한이 걸린 건물과 경계(1, n)만 관리하여 문제 크기를 m(제한 개수)로 축소했습니다.
2. 양방향 제약 전파 (Two-Pass): 한쪽 방향만 보면 놓치는 제약이 있습니다. 왼쪽→오른쪽(오르막 제약), 오른쪽→왼쪽(내리막 제약)을 모두 적용해야 각 지점의 진짜 최대 허용 높이를 알 수 있습니다.
3. 산봉우리 공식 (d + h1 + h2) // 2: 기울기가 ±1인 두 선분이 만나는 최고점 높이를 수식으로 계산하여, 구간 내 모든 건물을 시뮬레이션하지 않고 O(1)에 최대 높이를 구했습니다.

풀이 코드

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        restrictions.append([1,0])
        restrictions.sort()

        if restrictions[-1][0] != n:
            restrictions.append([n, n - 1])

        for i in range(1, len(restrictions)):
            id1, h1 = restrictions[i-1]
            id2, h2 = restrictions[i]
            restrictions[i][1] = min(h2, h1 + (id2 - id1))

        for i in range(len(restrictions) - 2, -1, -1):
            id1, h1 = restrictions[i]
            id2, h2 = restrictions[i+1]
            restrictions[i][1] = min(h1, h2 + (id2 - id1))

        answer = 0
        for i in range(1, len(restrictions)):
            id1, h1 = restrictions[i-1]
            id2, h2 = restrictions[i]

            answer = max(answer, (id2 - id1 + h1 + h2) // 2)

        return answer