99클럽 코테 스터디 10일차 TIL: 배열, Leetcode 451. Sort Characters By Frequency

문제

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

 

통과 여부

Pass

 

나의 접근법 

첫 번째 방법

class Solution:
    def frequencySort(self, s: str) -> str:
        
        # 문자 - 빈도수로 dict 초기화 : 중복되는 문자 제거
        char_frq = {}
        for ch in s:
            if ch in char_frq:
                char_frq[ch] += 1
            else:
                char_frq[ch] = 1
        
        # (빈도수, 문자) 쌍을 갖는 배열을 빈도수 내림차순으로 정렬
        tmp = []    
        for k, v in char_frq.items():
            tmp.append((v, k))
        tmp.sort(reverse=True)
        
        # 각 문자를 빈도수만큼 추가하여 join() 으로 연결
        ans = []
        for f, c in tmp:
            ans.extend([c]*f)
            
        return ''.join(ans)

 

두 번쨰 방법

class Solution:
    def frequencySort(self, s: str) -> str:
        
        # 빈도수와 일치하는 index 순서에 각 문자 추가
        frq = [[] for _ in range((len(s) + 1))]
        for ch in set(s):
            i = s.count(ch)
            frq[i].append(ch)
        
        # 역순으로 문자열을 인덱스 크기만큼 반복하여 집어넣기
        ans = []
        for j in range(len(frq)-1, 0, -1):
            for e in frq[j]:
                ans.extend([e]*j)
            
        return ''.join(ans)

 

시간복잡도 측면에서 둘 다 크게 차이가 나진 않았다.

확실히 시간 제약만 여유있다면 배열을 다루는 문제에서는 python 이 더 효과적인 것 같다.