.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์„ ์ƒ๊ฐํ•˜์ง€ ๋ชปํ–ˆ๋‹ค๋ฉด ์กฐ๊ธˆ ๋”๋Ÿฌ์šด ์ฝ”๋“œ๊ฐ€ ๋์„ ๊ฐ€๋Šฅ์„ฑ์ด ํฌ๋‹ค.
  • ๊ทธ๋ฆฌ๊ณ  ์™œ์ด๋ ‡๊ฒŒ ๋น ๋ฅด์ง€?
0 Comments
๋Œ“๊ธ€์“ฐ๊ธฐ ํผ