관리 메뉴

.Zzumbong

[leetCode/JS] 451. Sort Characters By Frequency 본문

coding test/leetCode

[leetCode/JS] 451. Sort Characters By Frequency

쭘봉 2022. 12. 3. 15:28

난이도 [ 🤔 ] Medium

 

문제 설명 

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.

문자열 s에 문자가 등장횟수만큼 내림차순 정렬한다. 
aaaccc, cccaaa 는 둘다 정답이란다. 숫자만 신경쓰면 된다.

 

입출력 예

Example 1:

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.

 

Example 2:

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.

 

Example 3:

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.

 

Constraints

  • 1 <= s.length <= 5 * 105
  • s consists of uppercase and lowercase English letters and digits.

 

 

 


 

내 솔루션

  • 문자열을 hasmap으로 문자를 key로, 등장 숫자를 value로 만든 후
  • 오름차순으로 sorting 한다.
  • map으로 repeat하여 반복시킨 후 배열을 join해서 문자열로 리턴한다.
/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
  // s = tree
  const map = {}
  for(const str of s) {
    map[str] = (map[str] || 0) + 1;
  }
  // map: { t: 1, r: 1, e: 2 }
  return Object.entries(map)
    .sort((a, b) => b[1] - a[1]) // [ [ 'e', 2 ], [ 't', 1 ], [ 'r', 1 ] ]
    .map(s => s[0].repeat(s[1])) // [e, e, r, t]
    .join(''); // 'eert'
};

 

감상평

  • 생각보다 까다로웠다. 
  • reduce를 쓸지 그냥 for 문으로 돌릴지 조금 느리더라도 이쁘게 만들지?
  • 고민하는 시간이 좀걸렸다. repeat을 생각하지 못했다면 조금 더러운 코드가 됐을 가능성이 크다.
  • 그리고 왜이렇게 빠르지?
Comments