[leetcode] 451. 빈도순으로 문자 정렬

문제

문자열이 주어졌을 때, 문자의 빈도를 기준으로 내림차순으로 정렬하세요. 문자의 빈도는 문자열에 나타나는 횟수입니다.

 

입출력

입력 s = "tree"

출력 "eert"

설명 'e'는 두번 나타나는 반면 'r'과 't'는 모두 한 번씩 나타납니다.

따라서 'e'는 'r'과 't' 앞에 모두 나와야 합니다. 따라서 'eetr'도 유효한 답입니다.

 

입력 s = "cccaaa"

출력 'aaaccc"

설명 'c'와 'a'가 모두 세번씩 등장하므로'cccaaa'와 'aaaccc'는 모두 유효한 답입니다.

 

입력 s = "Aabb"

출력 "bbAa"

설명 "bbaA"도 유효한 답이지만, "Aabb"는 틀린답입니다.

"A"와 'a'는 서로 다른 문자로 처리됩니다.

 

제약 조건

1 <= s.length <= 5* 10 5승

s 대문자, 소문자, 영어문자와, 숫자로 구성

 

어떻게 풀까?

빈도수를 넣기위해 사용하기좋은 자료구조는? hashmap

왜 그럴까요 ? hashmap은 o(1) 시간에 데이터를 저장하고 조회할수있기때문에 

 

1. hashmap의 key가 있다면 value +

2. 없다면 새로넣기

3. value가 제일많은것부터 key기준으로 배열 정렬하기

 

 

3번이 조금 헷갈렸지만

 

's' 2 'v' 3 'x' 2  

이렇게있다면 어떻게 [v, x, s] 이기준으로 value 값크기 기준으로 순서를 정렬할수있을까?

sort로 가능했다. 

단, sort를 쓰기위해서는 map.entries()로 객체를 꺼내서 배열을 만든후 정렬해주었다.

  const sortedKeys = [...map.entries()]
        .sort((a,b) => b[1] - a[1])
        .map(([k, v]) => k)

 

 

 

완성된코드

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
    const map = new Map();
    for(let val of s){
        if(map.has(val)){
            map.set(val, map.get(val) + 1); 
        }else{
            map.set(val, 1);
        }
    }

    let result = "";

    const sortedKeys = [...map.entries()]
        .sort((a,b) => b[1] - a[1])
        .map(([k, v]) => k)

    for(const key of sortedKeys){
        const loop = map.get(key);
        for(let i=0; i<loop; i++){
            result += key;
        }
    }

    return result;
};

 

 

 

다시한번 map을 다양하게 꺼내보고 써보는 계기가된코드이다.