LeetCode 1840. Maximum Building Height

LeetCode 1840. Maximum Building Height

«문제 링크 : https://leetcode.com/problems/maximum-building-height/»

---

아이디어

처음에는 "restrictions"에 적혀 있는 높이가 각 건물의 실제 최대 높이라고 생각했다.

하지만 뒤쪽에 있는 building의 최대 높이가 훨씬 낮다면, 인접한 건물의 높이 차이는 최대 1이라는 조건 때문에 앞쪽 building 역시 높이가 강제로 낮아질 수 있다.

즉, "restrictions"에 적혀 있는 높이는 실제 가능한 최대 높이가 아니라 독립적인 제한 조건일 뿐이다.

따라서 먼저 모든 제한 조건을 실제 가능한 최대 높이로 보정해야 했다.

---

1. 뒤에서부터 제한 조건 보정

먼저 building 번호 기준으로 정렬한다.

이후 뒤에서부터 순회하며 다음 제한 조건과의 거리를 계산한다.

count = nextIndex - currentIndex;
diff = currentHeight - nextHeight;

만약

diff > count

라면 현재 높이는 불가능한 값이므로

currentHeight -= (diff - count);

만큼 줄여 실제 가능한 최대 높이로 수정한다.

이 과정을 끝까지 반복하면 모든 제한 조건이 서로 모순되지 않는 값이 된다.

---

2. 각 구간의 최대 높이 계산

현재 위치와 다음 제한 조건 사이의 거리와 높이 차이를 이용한다.

count = restrictions[i][0] - nowIndex;
diff = restrictions[i][1] - nowHeight;

내려가는 횟수를

b = count - diff;

라고 두었다.

• "b <= 0"이면 계속 증가만 하면 된다.
• 그렇지 않다면 올라가는 구간과 내려가는 구간으로 나누어 최고점을 계산한다.

if (b % 2 != 0) {
    b--;
    count--;
}

b /= 2;
int a = count - b;

answer = max(answer, nowHeight + a);

---

3. 마지막 구간

모든 제한 조건 이후에도 building이 남아 있다면 제한이 없으므로 계속 1씩 증가시킨다.

answer = max(answer, nowHeight + (n - nowIndex));

---

시간 복잡도

• 정렬 : O(m log m)
• 앞에서 한 번, 뒤에서 한 번 순회 : O(m)

따라서 전체 시간 복잡도는 O(m log m) 이다.

---

전체 코드

class Solution {
public:
    typedef vector<int>vi;
    typedef vector<vi>vii;

    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        if (restrictions.size() == 0){
            return n - 1;
        }

        sort(restrictions.begin(), restrictions.end(), [](vi& o1, vi& o2){
            return o1[0] < o2[0];
        });

        int answer = 0;

        for (int i = (int)restrictions.size() - 2; i >= 0; i--) {
            if (!(restrictions[i][1] > restrictions[i + 1][1])) {
                continue;
            }

            int count = restrictions[i + 1][0] - restrictions[i][0];
            int diff = restrictions[i][1] - restrictions[i + 1][1];

            if (count < diff) {
                restrictions[i][1] -= (diff - count);
            }
        }

        int nowHeight = 0;
        int nowIndex = 1;

        for (int i = 0; i < restrictions.size(); i++) {
            int count = restrictions[i][0] - nowIndex;
            int diff = restrictions[i][1] - nowHeight;

            int b = count - diff;

            if (b <= 0) {
                nowHeight += count;
                nowIndex = restrictions[i][0];
                answer = max(answer, nowHeight);
                continue;
            }

            if (b % 2 != 0) {
                b--;
                count--;
            }

            b /= 2;
            int a = count - b;

            answer = max(answer, nowHeight + a);

            nowIndex = restrictions[i][0];
            nowHeight += (a - b);
        }

        if (nowIndex != n) {
            int count = n - nowIndex;
            answer = max(answer, nowHeight + count);
        }

        return answer;
    }
};

---

마무리

이 문제의 핵심은 봉우리의 높이를 계산하는 수식보다 "restrictions"의 높이가 실제 최대 높이가 아닐 수도 있다는 점을 발견하는 것이었다.

뒤쪽의 더 강한 제한이 앞쪽 제한을 무효화할 수 있기 때문에, 먼저 모든 제한 조건을 실제 가능한 최대 높이로 보정해야 이후 계산을 진행할 수 있었다.

수식보다 문제를 어떻게 해석하느냐가 더 중요했던 문제였다.