LeetCode [1636]: Sort Array by Increasing Frequency

📌 LeetCode [1636]: Sort Array by Increasing Frequency

🔗 문제 링크

---

문제 설명 📄

주어진 정수 배열 nums를 다음 규칙에 따라 정렬합니다:

1. 각 숫자의 빈도수에 따라 오름차순으로 정렬합니다.
2. 빈도수가 동일한 경우, 숫자를 내림차순으로 정렬합니다.

정렬된 배열을 반환하세요.

---

문제 접근 방식 📋

1. 각 숫자의 빈도를 계산하기 위해 Counter를 사용합니다.
2. 빈도수를 기준으로 정렬하고, 동일한 빈도수일 경우 숫자를 내림차순으로 정렬합니다.
3. 정렬된 결과를 기반으로 새로운 리스트를 생성합니다.

---

Solution 💻

from collections import Counter

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        count = Counter(nums)
        answer = []

        for key, value in sorted(count.items(), key=lambda x: (x[1], -x[0])):
            for i in range(value): 
                answer.append(key)

        return answer

시간 복잡도 분석 ⏲️

• 빈도 계산: (O(n)), (n)은 배열의 크기.
• 정렬: (O(k \log k)), (k)는 고유한 숫자의 개수.
• 결과 생성: (O(n)), 빈도수만큼 반복.
• 최종 시간 복잡도: (O(n + k \log k + n)).

공간 복잡도 분석 🗄️

• Counter 사용 공간: (O(k)), 고유 숫자의 개수.
• 결과 배열: (O(n)).
• 총 공간 복잡도: (O(n)).

---

리팩토링 🛠️

개선된 코드

from collections import Counter

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        count = Counter(nums)

        return sorted(nums, key=lambda x: (count[x], -x))

리팩토링 후 시간 복잡도 ⏲️

• 정렬: (O(n \log n)), 모든 숫자를 직접 정렬.
• 총 시간 복잡도: (O(n \log n)), 고유 숫자의 개수가 많아도 (O(n))보다는 효율적.

리팩토링 후 공간 복잡도 🗄️

• Counter 사용 공간: (O(k)), 고유 숫자의 개수.
• 총 공간 복잡도: (O(k)).

---