99클럽 코테 스터디 31일차 TIL + 문자열(Sort Characters By Frequency)

오늘의 과제

리트코드 medium으로 분류된 Sort Characters By Frequency 입니다.

 

이번 유형은 문자열 입니다.

문제

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

 

 

먼저 문제 요구사항 요약입니다.

 

문자열이 주어지면 문자의 빈도에 따라 내림차순으로 정렬 후 반환하면 됩니다.

 

입력 제한은 영어 대문자 소문자 숫자로 구성되어 있으며 최대 5 * 10⁵ 길이를 갖고 있으니 O(n²)으로는 풀 수 없습니다.

 

접근입니다. "문자 빈도"에 따라 문자열을 정렬해야 하니 단순한 생각으로 문자를 먼저 계산합니다. 각 문자에 대한 카운팅은 여러가지 방법이 있겠으나 저는 map을 활용하여 풀이하였습니다. map에서 제공하는 api 중 getOrDefault를 활용하여 없으면 0으로 넣어주고, 있으면 기존 값을 가져와 + 1 해주는 형태로 값을 쌓아갑니다.

var map = new HashMap<Character, Integer>();

for (char c : s.toCharArray()) {
    map.put(c, map.getOrDefault(c, 0) + 1);
}

 

 

값을 쌓아줬다면 map 내 value를 뽑아내어 내림차순으로 정렬해야 하는데 이 역시 Collections API에서 제공하는 sort 함수를 통해 해결합니다.

var keySet = new ArrayList<>(map.keySet());
keySet.sort((o1, o2) -> map.get(o2) - map.get(o1));

 

 

내림차순으로 정렬된 문자 리스트를 얻었다면, 이제 각 key에 대한 value만큼 문자를 쌓아 반환하면 됩니다.

var sb = new StringBuilder();
for (char c : keySet) {
    sb.append(String.valueOf(c).repeat(map.get(c)));
}

return sb.toString();

 

 

 

코드입니다.

import java.util.*;

class Solution {
    public String frequencySort(String s) {
        var map = new HashMap<Character, Integer>();

        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        var keySet = new ArrayList<>(map.keySet());
        keySet.sort((o1, o2) -> map.get(o2) - map.get(o1));

        var sb = new StringBuilder();
        for (char c : keySet) {
            sb.append(String.valueOf(c).repeat(map.get(c)));
        }
        
        return sb.toString();
    }
}

 

배운 점

항해99측에서 추천하는 풀이 시간이 45분이었는데 확실히 난이도가 낮았던 문제였습니다. 구현이 쉬웠던 이유도 있으나 문제 자체가 뭘 원하는지 명확해서 그랬던 영향 또한 있었습니다. 

 

대부분의 문제 풀이를 JDK 자체에서 제공하는 라이브러리 함수를 이용하여 풀었는데 자료구조라는 CS 지식 외에도 여러 함수를 사용해본 경험을 통해 실무에서도 유용하게 적용할 수 있을 것 같네요.

 

 

오늘의 한줄평

세상엔 이미 많은 것들이 만들어져 있다.
그것들을 적재 적소에 활용하는 것 또한 개발자의 중요한 능력이다.