[2024] day 131. Leetcode 3075. Maximize Happiness of Selected Children

gunny·2024년 5월 9일

leetcode 3075. Maximize Happiness of Selected Children leetcode 3075. Maximize Happiness of Selected Children python

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 9일 (목)
Leetcode daily problem

3075. Maximize Happiness of Selected Children

https://leetcode.com/problems/maximize-happiness-of-selected-children/?envType=daily-question&envId=2024-05-09

Problem

길이 n의 happiness 배열과 양의 정수 k가 제공될 때,
happiness 배열의 n은 n명의 아이들이 줄을 서 있고, i번째 아이의 happiness[i]는 happiness value 를 나타낸다.
k 차례에 걸쳐 n명의 어린이 중에서 k명의 어린이를 선택하려고 한다.
매 턴마다 한 아이를 선택하면 지금까지 선택되지 않은 모든 아이의 행복값이 1씩 감소한다. 행복값은 음수가 될 수 없으며 양수일 경우에만 감소한다.

k명의 어린이를 선택하여 달성할 수 있는 선택된 어린이의 행복값의 최대 합을 반환한다.

Solution

sort, greedy

행복값의 최대를 반환해야 하므로, 그리디 알고리즘을 사용하기 위해서
happiness 배열을 내림차순으로 정렬한다.

그 후에, k번만큼 순회하면서 happiness 배열에 있는 원소의 값을 더해가는데, k번 순회하면서의 턴을 따로 업데이트했다가 해당 원소에서 움직이는 턴만큼 빼줘서 감소한 행복 값을 더해줘야 한다.

Code

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort(reverse=True)
        n = 0
        ans = 0
        while k:
            ans += happiness[n]-n if happiness[n]-n >0 else 0
            n+=1
            k-=1
            
        return ans