[2024] day 38. 451. Sort Characters By Frequency

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

2024년 2월 7일 (수)
Leetcode daily problem

451. Sort Characters By Frequency

https://leetcode.com/problems/sort-characters-by-frequency/description/

Problem

문자열 s가 주어지면 문자 빈도에 따라 내림차순으로 정렬하고, 정렬된 문자열을 반환한다. 답변이 여러개 라면 그 중 하나만 반환한다.

Solution

array

Counter 함수를 사용해서 주어진 문자열을 key, 빈도 값을 value로 하는 해쉬맵을 하나 만들고 (딕셔너리 생성), 딕셔너리를 빈도인 value 값 기준으로 sort 한다. 생성한 해쉬맵을 돌면서 나왔던 빈도 만큼 문자열을 곱해 실제 문자열로 만든 후에 합성하여 마지막 결과 문자열을 반환한다.

Code

class Solution:
    def frequencySort(self, s: str) -> str:
        cnt = Counter(s)
        sortedCnt = sorted(cnt, key = cnt.get, reverse=True)
        ans = ''
        for c in sortedCnt:
            ans += c * cnt[c]

        return ans

Complexicity

시간 복잡도

Counter를 문자열의 빈도수를 계산하는 과정이 O(n)
배열을 정렬하는 과정에서 O(nlogn), 마지막 배열을 순회할 때 O(n)으로 최종 시간복잡도는 O(nlogn)이다.

공간 복잡도

해시맵을 사용하여 문자열을 저장할 때 O(n)을 사용하고,
정렬된 배열을 저장할 때 O(n)을 사용하므로 전체 코드의 공간복잡도는 O(n)이다.

---