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

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

Complexicity

시간 복잡도

주어진 happiness 배열을 정렬하는 과정에서 O(n log n)이 소요된다. 총 시간복잡도는 O(nlogn)이다.

공간 복잡도

새로운 변수에 상수 개수 만큼 사용하므로 추가 적인 공간은 필요하지 않아 공간 복잡도는 O(1)이다.