[LeetCode] Minimum Deletions To Make Character Frequencies Unique

문제링크

Minimum Deletions to Make Character Frequencies Unique - LeetCode

 

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;
};