1. 문제 소개

3075. Maximize Happiness of Selected Children

2. 나의 풀이

순간순간의 최고의 선택이 결국 최적해가 된다는 Greedy Algorithm을 적용해 바로 풀었다.
시간복잡도는 정렬에 쓰인 $O(n\, log n)$이다.

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort()                              # 행복도를 오름차순으로 정렬(가장 큰 값부터 선택하기 위함)
        ans, cnt = 0, 0                               # ans: 누적 행복도 합, cnt: 이미 선택한 아이 수
        
        while cnt < k:                                # k명을 선택할 때까지 반복
            max_happy = happiness.pop()               # 현재 남아 있는 아이 중 가장 큰 행복도 선택
            ans += max_happy - cnt if max_happy - cnt > 0 else 0
                                                      # 선택 순서로 인한 감소(cnt)를 반영한 실제 기여도 추가
                                                      # 음수가 되면 0으로 처리
            cnt += 1                                  # 선택한 아이 수 증가

        return ans                                    # 최대 행복도 합 반환

3. 다른 풀이

heap을 사용한 풀이도 존재한다.
시간복잡도는 $O(n+k\,logn)$이다.

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        # Python의 heapq는 최소 힙(min-heap)이므로,
        # 최대 힙처럼 사용하기 위해 각 행복도 값에 -를 붙여 변환한다.
        max_heap = [-h for h in happiness]

        # 리스트를 힙 구조로 변환 (O(n))
        heapq.heapify(max_heap)
        
        total_happiness_sum = 0  # 최종 행복도 합
        turns = 0                # 이미 선택된 아이 수(= 이후 감소량)

        # 정확히 k명의 아이를 선택
        for _ in range(k):
            # 현재 가장 큰 행복도를 가진 아이를 선택
            # -heapq.heappop(max_heap): 원래의 최대 행복도 값
            # turns만큼 감소된 실제 기여도 계산
            total_happiness_sum += max(-heapq.heappop(max_heap) - turns, 0)

            # 다음 선택부터는 감소량이 1 증가
            turns += 1
            
        return total_happiness_sum

4. 마무리

시간복잡도 측면에서는 정렬이 힙보다는 낫다.