[리트코드] 1647. Minimum Deletions to Make Character Frequencies Unique / Javascript

문제주소 :https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/

Minimum Deletions to Make Character Frequencies Unique - LeetCode

---

<문제 설명>

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

 

Example 1:

Input: s = "aab" Output: 0 Explanation: s is already good.

Example 2:

Input: s = "aaabbbcc" Output: 2 Explanation: You can delete two 'b's resulting in the good string "aaabcc". Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".

Example 3:

Input: s = "ceabaacb" Output: 2 Explanation: You can delete both 'c's resulting in the good string "eabaab". Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

 

Constraints:

• 1 <= s.length <= 105
• s contains only lowercase English letters.

 

<풀이법>

▒ 한줄 개념: First-Fit ▒ 

메모리 관리 기법 중 First-Fit 방식이 생각나서 그걸 적용해서 풀어봤습니다.

문제가 풀리긴 했으나 좋은 방식은 아닌 것 같습니다.

풀이 방식은 다음과 같습니다.

 

1. char 별 등장 횟수 계산

2. 횟수들을 순서대로 탐색하며 First-Fit 방식을 사용하여 계산

 

<코드(Javascript)>

/**
 * @param {string} s
 * @return {number}
 */
var minDeletions = function(s) {
    let answer = 0;
    const arr = s.split('');
    const dict = {};
    const mem = [];
    arr.map(char => {
        dict[char] = dict[char] ? dict[char] + 1 : 1;
    })
    const values = Object.values(dict);
    values.map(v => {
        if(mem[v]){
            let nextPos = v;
            while(nextPos > 0){
                if(!mem[nextPos]){
                    mem[nextPos] = true;
                    answer += v - nextPos;
                    break;
                }else{
                    nextPos--;
                }
            }
            if(nextPos === 0){
                answer += v;
            }
        }else{
            mem[v] = true;
        }
    })
    return answer;
};

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest