Daily Leetcoding Challenge 1647. Minimum Deletions to Make Character Frequencies Unique

 

리트코드 서버가 UTC로 설정돼 있어서 매일 오전 9시에 날짜가 넘어간다. 그래서 아침에 워밍업으로 풀기에 적당한 것 같다. (어렵지 않은 것만..ㅎㅎ)

https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique

Minimum Deletions to Make Character Frequencies Unique - LeetCode

 

직관

주어진 문자열에 출현한 문자들의 반복 횟수가 중복되면 안 된다. 그리고 문자열은 알파벳 소문자로만 이뤄져 있다. 반복 횟수가 유니크가 되기 위해 문자를 제거해야 하기 때문에, 문자열 반복 횟수를 계산하고 정렬하면 제거해야 하는 문자 개수를 카운트하기 쉬울 것 같았다.

접근법

크기가 26(알파벳 개수)인 freq 배열을 선언하고,  문자열을 돌면서 문자가 출현한 횟수를 구한다.

freq 배열을 정렬한다.

freq 값이 큰 것부터 작은 것으로 차례대로 순회하면서 다음을 확인한다:

  - freq[i]가 0이면 반복문을 탈출한다. (정렬했기 때문에 더 이상 출현한 알파벳이 없다)

  - freqSet에 freq[i]가 존재하지 않는다면 freqSet에 추가한다. (unique한 출현 횟수라서)

  - freqSet에 이미 freq[i]가 있다면, freqSet에 freq[i]가 존재하지 않으면서 freq[i]가 0보다 크도록 freq[i]를 1씩 줄이고, removal은 1씩 증가시킨다.

removal을 리턴한다.

복잡도

시간복잡도 구할 때마다 이런 반복문이 있으면 머리가 하얘지는것 같다. 😱 우선 문자열의 길이를 n이라고 했을 때, 빈도수를 계산하기 위해 문자열을 순회하는 데에 필요한 시간이 O(n). 그리고 freq 배열을 정렬하는데 필요한 시간 O(26) = O(1). 그리고 freq를 순회하면서 중복된 빈도수가 있으면 반복문을 돌면서 freq[i]를 1씩 줄이는 코드가 있다. 이때 최악의 경우를 생각해 보면,

'26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26'

문자열에 출현한 알파벳 모두 빈도수가 같은 경우일 것이다.

i = 24일 때, freqSet 26 (1)

i = 23일 때, freqSet 26 25 (2)

i = 22일 때, freqSet 26 25 24 (3)

...

i = 0 일 때, 26 25 24 23 22 21 20 19 18 17 ... 2 (25)

25 * 26 / 2 = 325회 계산이 필요하다.

그런데 freq 배열의 크기는 문자열의 길이 n에 상관없이 고정돼 있다. 따라서 이 계산 역시 Big O notation으로는 O(1)이다.

그래서 시간 복잡도는 O(n)이다.

공간 복잡도는 freq 저장공간 O(1), freqSet이 저장하는 빈도수도 많아야 26이라서 O(1)이다.

코드

class Solution {
    public int minDeletions(String s) {
        int[] freq = new int[26];
        for(char c : s.toCharArray()) {
            freq[c-'a'] += 1;
        }
        Arrays.sort(freq);
        int removal = 0;
        Set<Integer> freqSet = new HashSet<>();
        freqSet.add(freq[25]);
        for(int i=24; i>=0; i--) {
            if (freq[i] == 0) {
                break;
            } else if (!freqSet.contains(freq[i])) {
                freqSet.add(freq[i]);
            } else {
                while(freq[i] > 0 && freqSet.contains(freq[i])) {
                    freq[i] -= 1;
                    removal += 1;
                }
                freqSet.add(freq[i]);
            }
        }
        return removal;
    }
}