๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/LeetCode

[LeetCode] Minimum Deletions To Make Character Frequencies Unique

๋ฌธ์ œ๋งํฌ

 

Minimum Deletions to Make Character Frequencies Unique - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

aaaabbbccd ์ฒ˜๋Ÿผ ํ•œ ๋ฌธ์ž๊ฐ€ n๊ฐœ ์žˆ์œผ๋ฉด ๋‹ค๋ฅธ ๋ฌธ์ž๋Š” n๊ฐœ๊ฐ€ ์žˆ์œผ๋ฉด ์•ˆ๋œ๋‹ค๋Š” ๊ทœ์น™์„ ๋งŒ์กฑ์‹œํ‚ค๋„๋ก ์ฃผ์–ด์ง„ ๋ฌธ์ž s๋ฅผ ํ•ธ๋“ค๋ง ํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.
s์— ๊ฐ™์€ ๊ฐฏ์ˆ˜์˜ ๋ฌธ์ž๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š๋„๋ก ํ•˜๊ธฐ ์œ„ํ•ด ์ง€์›Œ์•ผํ•  ๋ฌธ์ž์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•ด๋ผ.

์ ‘๊ทผ ๋ฐฉ๋ฒ•

๋จผ์ € ์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด s์˜ ๊ฐ ๋ฌธ์ž๋ณ„ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•ด์„œ ์ƒˆ๋กœ์šด ๋ฐฐ์—ด์— ๋„ฃ๋Š”๋‹ค.

// sArr : ๋ฌธ์ž์—ด์„ ๋ฐฐ์—ด๋กœ ๋ณ€ํ™˜ํ•˜์—ฌ ์ •๋ ฌํ•œ ๋ฐฐ์—ด
// cntArr : ๋ฌธ์ž๋ณ„ ๊ฐฏ์ˆ˜๋ฅผ ๋‹ด์€ ๋ฐฐ์—ด

for(let i = 1; i < sArr.length; i++){
  if(sArr[i-1] === sArr[i]) sameWordCnt++;
  else{
      cntArr.push(sameWordCnt);
      sameWordCnt = 1;
  }
}
cntArr.push(sameWordCnt)โ€‹

๋‹ค์Œ์œผ๋กœ ๋ฌธ์ž์˜ ์ˆ˜๋ฅผ ๋‹ด์€ ๋ฐฐ์—ด cntArr์„ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.
cntArr.sort((a,b) => b - a)โ€‹

๋งˆ์ง€๋ง‰์œผ๋กœ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ ๋ฐฐ์—ด์„ ์ˆœํ™˜ํ•˜๋ฉฐ ์ด์ „ ๊ฐ’๊ณผ ๋‹ค์Œ ๊ฐ’์„ ๋น„๊ตํ•˜์—ฌ ๋‹ต์„ ๊ตฌํ•œ๋‹ค.
(๋งŒ์•ฝ [1, 3] ์ด๋ผ๋ฉด cntArr[0] <= cntArr[1] ์ด๋ฏ€๋กœ cntArr[0] <= cntArr[1]์ด ๋งŒ์กฑํ•˜์ง€ ์•Š์„๋•Œ๊นŒ์ง€ cntArr[1]์„ ๋บ€๋‹ค.)
([2,2,2,2] ๊ฐ™์€ ๋ฐฐ์—ด์ด ์˜จ๋‹ค๋ฉด [2,1,0,-1]์ด๋ž€ ๊ฐ’์ด ๋‚˜์˜ฌ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ cntArr[i] !== 0์ผ ๊ฒฝ์šฐ๋งŒ ๊ตฌํ•œ๋‹ค.) 
for(let i = 1; i < cntArr.length; i++){
  while(cntArr[i-1] <= cntArr[i] && cntArr[i] !== 0){
      cntArr[i] -= 1;
      output++;
  }
}โ€‹

 

/**
 * @param {string} s
 * @return {number}
 */
 var minDeletions = function(s) {
  let sArr = s.split("").sort();
  let sameWordCnt = 1;
  let cntArr = [];
  let output = 0;
  
  for(let i = 1; i < sArr.length; i++){
      if(sArr[i-1] === sArr[i]) sameWordCnt++;
      else{
          cntArr.push(sameWordCnt);
          sameWordCnt = 1;
      }
  }
  cntArr.push(sameWordCnt)
  
  cntArr.sort((a,b) => b - a)
  
  for(let i = 1; i < cntArr.length; i++){
      while(cntArr[i-1] <= cntArr[i] && cntArr[i] !== 0){
          cntArr[i] -= 1;
          output++;
      }
  }
  
  return output;
};

 

'์ฝ”๋”ฉํ…Œ์ŠคํŠธ > LeetCode' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[LeetCode] Maximum Bags With Full Capacity Of Rocks  (0) 2022.07.02
[LeetCode] Maximum Units On A Truck  (0) 2022.07.01
[LeetCode]Maximum Points You Can Obtain From Cards  (0) 2022.06.26
[LeetCode] Non-decreasing Array  (0) 2022.06.25
[LeetCode] Valid Parentheses  (0) 2022.06.24