[LeetCode] 451 Sort Characters By Frequency

💡 오늘의 학습 키워드

📌  문자열

 

문제 설명

문제 링크 : https://leetcode.com/problems/sort-characters-by-frequency/

Given a string s, sort it in decreasing order based on the frequency of the characters.
The frequency of a character is the number of times it appears in the string.
Return the sorted string. If there are multiple answers, return any of them.

제한 사항
1. 1 <= s.length <= 5 * 10^5
2. s consists of uppercase and lowercase English letters and digits.

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

주어진 string 값의 문자의 개수를 비교하여 많은 순서대로 출력해주면 간단히 풀리는 문제였습니다.
다만 이 과정에서 문자열에 문자를 분류하고 개수를 측정하여 내림차순으로 정렬하는데에 최소한의 구현력이 필요한 부분이 있습니다.

먼저 문자열의 문자를 개수를 분류하기 위해서는 딕셔너리에 key, value 값에 저장하는게 가장 효율적입니다.
이 때 defaultdict를 이용하면 초기화를 간결하게 할 수 있습니다.
value에 문자의 개수, 즉 정수를 저장하게 되므로 int로 초기화 해줍니다.

반복문을 통해 문자의 개수를 분류하고 나면 해당 딕셔너리를 내림차순으로 정렬해야 합니다.
value 값을 기준으로 내림차순 해야 하므로 key 값을 기준으로 정렬되는 방식에 약간의 응용이 필요합니다.
lambda 를 이용하여 아래의 조건을 sorted 함수에 매개변수로 추가해줍니다.

s_cnt = sorted(s_cnt.items(), key=lambda x: x[1], reverse=True)

이렇게 추가하게 되면 x[1], 즉 딕셔너리 s_cnt의 두 번째 값인 value 값을 비교할 수 있게 됩니다.
이제 reverse=True를 추가하게 되면 value 값을 기준으로 내림차순 된 딕셔너리가 만들어집니다.

정렬된 딕셔너리를 key 값과 value 값을 곱하여 string 타입으로 반복문을 순회하여 더해주게 되면 원하는 결과 값을 반환할 수 있습니다.

 

💡 내가 해결한 방식은?

딕셔너리 value 값 내림차순을 이용한 풀이

from collections import defaultdict

class Solution:
    def frequencySort(self, s: str) -> str:
        s_cnt = defaultdict(int)
        for alph in s:
            s_cnt[alph] += 1

        result = ""

        # 내림차순 정렬
        s_cnt = sorted(s_cnt.items(), key=lambda x: x[1], reverse=True)

        # 조건에 맞게 정렬
        for key, value in s_cnt:
            result  += key * value
        
        return result

 

---

✍️ TIL

딕셔너리의 활용이 익숙해지는데 도움이 되었던 문제였다. 동일한 개수에서도 별도의 정렬이 필요할 줄 알았는데
문제를 다시 읽어보니 return any of them이 보여 그냥 제출하여 문제를 해결할 수 있었다.
lambda 는 언제 사용해도 익숙해지지 않는데 이제 defaultdict를 사용하기 이전이 기억나지 않는다.
딕셔너리에서 key, value를 기준으로 정렬하는 과정을 숙지할 수 있었고, 오랜만에 빠르게 정답을 이끌어낸 문제라 
꿀잠 잘 수 있을 것 같다.