[2024] day 69. Leetcode 3005. Count Elements With Maximum Frequency

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

2024년 3월 8일 (금)
Leetcode daily problem

3005. Count Elements With Maximum Frequency

https://leetcode.com/problems/count-elements-with-maximum-frequency/description/

Problem

양의 정수로 구성된 배열 nums가 제공 될때,
배열 내의 원소 들 중 최대 빈도수를 갖는 원소의 총 빈도를 숫자로 반환한다.
요소의 빈도는 배열에서 각 원소들이 나타나는 횟수이다.

예를 들어 nums=[1,2,2,3,1,4] 라는 배열이 주어졌을 때,
해당 배열의 각 빈도는 1원소 2번, 2원소 2번, 3원소 1번, 4원소 1번이다.
해당 배열의 최대 빈도수는 2번이고, 2번 빈도를 가진 원소가 1 원소 2개, 2원소 2개를 가지고 있어
총 빈도수는 4이다.

또 nums=[1,2,3,4,5] 배열에서는 각 원소들이 1회씩만 등장하였고,
최대 빈도수는 1이므로 1번씩 등장한 원소 수가 5개로 총 빈도수는 5이다.

Solution

array

처음 푼 방법은 Counter를 쓰지 않고 주어진 배열의 원소의 max 값을
사이즈로 하는 리스트를 만들어, 배열을 탐색하면서 주어진 원소의 빈도 수를 맵으로 업데이트 했다.

그리고 해당 빈도수의 맵을 value 값으로 내림차순해서
해당 맵의 가장 첫 번째 수가 최대 빈도수 이므로, 맵을 탐색하면서 빈도수와 같으면
최대빈도수에 해당하는 원소들의 개수를 곱해서 총 빈도수를 반환하는 씩으로 코드를 구현했다.

제약사항에 nums[i]가 1부터 100까지 이기 때문에 아무리 해도 max 값이 100일 것 같아
빈도수를 저장하는 리스트 사이즈가 100을 넘어가지 않아 이렇게 구현했다.

그러나 만약 해당 제약사항의 수가 커진다면 빈도수 리스트의 사이즈가 대책없이 커질 것이라 해당 코드보다는
다른 코드가 더 좋아보여, 하단에 해당 코드를 보고 다시 구현했다.

Code

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        if len(set(nums)) == len(nums):
            return len(nums)

        cnt = [0] * (max(nums)+1)
        for n in nums:
            cnt[n] += 1

        cnt.sort(reverse=True)

        result, curNum = 0, 0
        for num in cnt:
            if curNum <= num:
                result += num
            else:
                break
            curNum = num

        return result

Complexicity

시간 복잡도

배열을 탐색할 때 O(n), sort하면서 배열 원소의 최대값이 m 이라면 O(mlogm)이 발생한다.
총 시간 복잡도는 O(n + mlogm)이다.

공간 복잡도

nums의 원소의 max값에 따라 배열이 사이즈가 생성되므로 O(n)의 공간복잡도를 가진다.

---

다른 풀이는

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        freqCnt = Counter(nums)
        maxFreq = max(freqCnt.values())
        maxFreqElements = [num for num, freq in freqCnt.items() if freq==maxFreq]
        
        return len(maxFreqElements) * maxFreq

이다. Counter 함수를 이용해서 배열 nums의 원소별 빈도수를 업데이트한다.
그리고 원소별 최대 빈도수를 maxFreq에 할당해 최대 빈도수를 업데이트한다.
원소별 빈도수 맵을 탐색하면서, 빈도수가 최대 빈도수와 같다면 해당 원소를 배열에 넣는다.
마지막으로 최대 빈도수와 최대빈도수와 같은 원소들의 길이를 곱해서 빈도 원소의 총 수를 반환한다.

해당 코드의 시간복잡도는 처음 nums를 탐색해서 빈도를 파악하므로 O(n),
빈도수에서 최대 빈도수를 찾는 O(m), 총 빈도수들의 맵을 탐색할 때 O(m)으로 O(n+m)이다.

해당 코드의 공간복잡도는 Counter 모듈로 생성되는 빈도수의 배열 O(n)과 최종 빈도수와 같은 원소를 담는 배열의 O(m)으로 총 공간복잡도는 O(n+m)이다.