[LeetCode] 451. Sort Characters By Frequency

문제 출처: https://leetcode.com/problems/sort-characters-by-frequency/

Sort Characters By Frequency - LeetCode

---

문제

문자열 s가 주어지면, 문자의 빈도수를 기반으로 내림차순으로 정렬하라. 문자의 빈도수는 문자열 내에 문자가 쓰인 횟수를 말한다.

 

정렬된 문자열을 반환하라. 만약 가능한 답이 여러 개라면, 그중 임의의 하나를 반환하라.

예제

Input: s = "tree"
Output: "eert"

Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Input: s = "cccaaa"
Output: "aaaccc"

Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Input: s = "Aabb"
Output: "bbAa"

Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

---

풀이

맵(Map) 자료구조를 사용하여 입력으로 주어진 문자열 s의 각 문자 빈도수를 카운팅 합니다.

var frequencySort = function(s) {
    const freqMap = new Map();
    for (let i = 0; i < s.length; i++) {
    	if (!freqMap.has(s[i])) { freqMap.set(s[i], 0); }
        freqMap.set(s[i], freqMap.get(s[i]) + 1);
    }
}

카운팅 결과를 토대로 정렬을 수행해야 합니다. 하지만, 맵 상태로는 정렬이 불가능합니다. 그래서 맵을 배열로 변환한 후 내림차순 정렬을 수행합니다.

var frequencySort = function(s) {
    const freqMap = new Map();
    for (let i = 0; i < s.length; i++) {
    	if (!freqMap.has(s[i])) { freqMap.set(s[i], 0); }
        freqMap.set(s[i], freqMap.get(s[i]) + 1);
    }
    
    const freqArr = Array.from(freqMap.entries());
    freqArr.sort((a, b) => b[1] - a[1]);
}

정렬된 배열을 순차적으로 접근하면서 그 빈도수만큼 문자를 생성하여 연결하는 것으로 문제의 답을 찾을 수 있습니다.

var frequencySort = function(s) {
    const freqMap = new Map();
    for (let i = 0; i < s.length; i++) {
    	if (!freqMap.has(s[i])) { freqMap.set(s[i], 0); }
        freqMap.set(s[i], freqMap.get(s[i]) + 1);
    }
    
    const freqArr = Array.from(freqMap.entries());
    freqArr.sort((a, b) => b[1] - a[1]);
    
    let answer = '';
    
    for (const [key, val] of freqArr) {
    	answer += key.repeat(val);
    }
    
    return answer;
}

시간 복잡도를 계산해보면, $O(NlogN)$이 됩니다. 위 알고리즘은 세 부분으로 나누어 생각할 수 있습니다.

• 빈도수 계산
• 내림차순 정렬
• 결과 문자열 생성

각각의 시간 복잡도를 생각해보면 빈도수 계산 $O(N)$, 내림차순 정렬 $O(N logN)$, 결과 문자열 생성 $O(N)$입니다. 그렇기 때문에 최종 전체 알고리즘의 시간 복잡도는 $O(N logN)$으로 생각할 수 있습니다.

 

Github: 451.js

GitHub - opwe37/Algorithm-Study