본문으로 건너뛰기

3085 - Minimum Deletions to Make String K-Special

info

풀이 키워드​

스포주의

해시 완전탐색 그리디


풀이 코드​

info
  • 메모리: 45300 KB
  • 시간: 7 ms
class Solution {
    public int minimumDeletions(String word, int k) {
        int[] cnt = new int[26];
        for (char ch : word.toCharArray()) {
            ++cnt[ch-'a'];
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < 26; ++i) {
            int t = cnt[i]; // base target
            int deleted = 0;
            for (int j = 0; j < 26; ++j) {
                int n = cnt[j];
                if (n < t) {
                    deleted += n; // delete all
                }
                else if (n-t > k) {
                    deleted += n - (t+k); // delete exceeded amounts
                }
            }
            ans = deleted < ans ? deleted : ans;
        }

        return ans;
    }
}

풀이 해설​

모든 문자를 해싱해서 카운팅한 뒤,

어느 한 문자의 개수(t)를 기준으로 잡고 다른 문자의 개수(n)와 비교하며 처리해야 한다.

비교시엔 크게 두 가지 경우가 있다.

  1. t보다 n이 큰 경우 -> 서로의 차가 k 이하인지 확인해야 함
  2. t보다 n이 작은 경우 -> 다 폐기

왜 2번에서 다 폐기하냐면, 1번에서 t보다 큰 애들은 k만큼 허용 범위를 뒀기 때문이다.

예를 들어 만약 어떤 한 문자가 t+k개면 1번에서 통과하는데,
2번에서 t보다 작은 n을 살려두면 t+k와 n과의 차가 k를 초과하게 돼서 안된다.


...이런식으로 쳐내지는 개수를 매 기준마다 deleted에 합산하고, 가장 작은 합산 값을 구하면 된다.

시각화는 Discussion에 있는 것을 참고하자. (정렬은 그냥 보기 좋으라고 해둔거)


메모​

  • 발상이 그리 쉽지만은 않다...
  • 기준만 잘~ 나누면 됨