고유한 탑의 총 높이 최대화: Python에서의 그리디 해법

고유한 탑의 최대 총 높이 만들기(LeetCode 3301)는 각 탑마다 최대 높이가 주어지는 문제입니다. 모든 탑에 대해 최대 높이를 넘지 않으면서 서로 다른 양의 정수 높이를 배정해야 합니다. 가능한 가장 큰 총 높이를 반환하고, 불가능하면 -1을 반환합니다. 정렬 후 그리디 접근으로 O(n log n)에 해결할 수 있습니다.

문제

배열 maximumHeight가 주어지며, maximumHeight[i]는 i번째 탑이 가질 수 있는 최대 높이입니다. 다음 조건을 만족하도록 height[i]를 정합니다:

• 1 <= height[i] <= maximumHeight[i]
• 모든 height[i] 값이 서로 다름

가능한 최대 합을 반환하고, 유효한 배정이 없으면 -1을 반환합니다.

예시:

아이디어

총합을 크게 만들려면 모든 탑을 최대한 높게 해야 합니다. 높이는 서로 달라야 하므로 순서를 생각해보세요: 가장 높이 세울 수 있는 탑에 가장 큰 값을 주고, 그다음 탑에는 그보다 작은 값 중 가장 큰 값을 주는 식입니다.

1. 최대 높이들을 내림차순으로 정렬합니다.
2. 첫 번째 탑에는 최대 높이를 그대로 줍니다.
3. 이후 각 탑에는 min(자기 최대 높이, 이전 높이 - 1)을 배정합니다.
4. 배정된 높이가 0 이하로 떨어지면 유효한 배정이 없으므로 -1을 반환합니다.
5. 높이들을 모두 더합니다.

def maximum_total_sum(maximum_height):
    total = 0
    limit = float("inf")
    for m in sorted(maximum_height, reverse=True):
        h = min(m, limit - 1)
        if h <= 0:
            return -1
        total += h
        limit = h
    return total

[2,3,4,3]에 대한 추적: 내림차순 정렬하면 [4,3,3,2]입니다. 높이: 4, 그다음 min(3, 3) = 3, 그다음 min(3, 2) = 2, 그다음 min(2, 1) = 1. 합은 10입니다.

그리디가 통하는 이유

교환 논증으로 보일 수 있습니다. 어떤 최적해가 더 큰 최대 높이를 가진 탑에 더 작은 최대 높이를 가진 탑보다 낮은 높이를 준다고 가정해봅시다. 두 높이를 맞바꿔도 각 탑의 제한을 벗어나지 않습니다. 최대 높이가 더 큰 탑은 더 작은 탑이 가질 수 있는 어떤 값이든 가질 수 있기 때문이며, 합도 변하지 않습니다. 따라서 어떤 최적해는 정렬된 최대 높이 순서와 같은 순서로 높이를 배정합니다.

순서가 정해지면, 각 탑은 자기 최대 높이보다 클 수 없고, 바로 앞 탑보다 1 작은 값보다 클 수 없습니다. 정확히 그 상한을 취하는 것이 최선입니다: 더 낮은 높이는 지금 합을 줄일 뿐만 아니라, 뒤의 탑들에게도 도움이 되지 않습니다. 뒤 탑들의 상한이 이 높이에 의존하므로, 이 값을 낮추면 뒤 탑들의 상한도 함께 낮아지기 때문입니다.

또한 2,000개의 무작위 소규모 배열에 대해 모든 배정을 탐색하는 브루트 포스와 코드를 대조해보았고, 답이 일치했습니다.

복잡도

• 시간: O(n log n), 정렬이 지배적입니다. 반복문은 O(n)입니다.
• 공간: 제자리 정렬을 하면 추가 O(1), 정렬된 복사본을 만들면 O(n)입니다.

다른 관점: 값의 개수

-1인 경우를 다르게 보는 방법도 있습니다: 정렬된 최대 높이가 m1 >= m2 >= ... >= mn일 때, 유효한 배정이 존재하려면 각 i에 대해 i번째로 큰 최대 높이가 최소 n - i + 1 이상이어야 합니다. 그 값 이하의 서로 다른 양의 정수가 그만큼 필요하기 때문입니다. 반복문은 진행하면서 이를 검사합니다.

엣지 케이스

Java나 C++에서는 최대 높이가 큰 탑이 많으면 총합이 32비트를 초과할 수 있으므로 long을 사용하세요.

면접에서 설명하는 방법

1. -1인 경우를 포함해 제약 조건을 다시 말합니다.
2. 높이가 서로 다른 높은 탑을 원하므로, 가장 큰 최대 높이부터 처리한다고 말합니다.
3. 규칙을 말합니다: 각 높이는 자기 최대 높이와 이전 높이 - 1 중 최솟값입니다.
4. 이유를 설명합니다: 탑 사이에 높이를 맞바꿔도 도움이 되지 않고, 각 선택이 가능한 가장 큰 값입니다.
5. 복잡도와 오버플로 주의사항을 말합니다.
6. [2,2,1], 원소 하나, 모두 같은 값인 경우로 테스트합니다.

관련 연습

비슷한 그리디 및 정렬 문제로는 Assign Cookies와 Minimum Number of Arrows to Burst Balloons가 있습니다. 연습을 체계화하는 방법은 Blind 75 학습 계획과 AI LeetCode 튜터 가이드를 참고하고, 복습 루틴은 코딩 인터뷰 어시스턴트 가이드를 참고하세요.

연습할 때 교환 논증을 소리 내어 설명해보세요. 모의 면접 기록을 보면 이유를 말했는지 코드만 제시했는지 알 수 있습니다. 실제 평가에서는 AI 도구에 관한 회사 규정을 따르세요.