[2024] day 204. 1636. Sort Array by Increasing Frequency

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

2024년 7월 23일 (화)
Leetcode daily problem

1636. Sort Array by Increasing Frequency

https://leetcode.com/problems/sort-array-by-increasing-frequency/?envType=daily-question&envId=2024-07-23

Problem

정수 배열이 주어지면 값의 빈도에 따라 오름차순으로 배열을 정렬한다. 여러 값의 빈도가 동일한 경우 내림차순으로 정렬하고 정렬된 배열을 반환한다.

Solution

Customized Sorting

주어진 배열(num)을 탐색하면서, 해당 배열의 원소의 빈도수를 저장할 딕셔너리(맵)을 업데이트한다.

그리고 주어진 배열(num)의 원소들을 빈도수를 저장한 딕셔너리(맵)에서 원소의 value에 해당하는 빈도수에 따라 정렬하고, 해당 원소인 key는 음수로 지정해서 빈도수에 따라 정렬됐지만 같은 빈도수의 경우 내림차순으로 정렬할 수 있도록 커스터마이징 한다.

Code

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        freq_map = {}
        for num in nums:
            freq_map[num] = freq_map.get(num,0)+1
            
        return sorted(nums, key=lambda x: (freq_map[x], -x))

Complexicity

시간 복잡도

nums 배열의 모든 요소를 한번씩 순회할 때 O(n) 이 소요되고, sorted 함수로 정렬할 때 O(nlogn)이 소요된다.
즉 전체 시간복잡도는 O(nlogn)이다.

공간 복잡도

공간복잡도는 nums의 고유한 요소의 수에 비례하고, 최악의 경우 모든 요소가 고유할 수 있어 전체 공간 복잡도는 O(n) 이다.