[Leetcode] 1647. Minimum Deletions to Make Character Frequencies Unique

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

---

문자열 s는 동일한 빈도를 가진 두 개의 다른 문자가 없으면 good이라 한다.

문자열 s 가 주어지면 s를 good 이라고 불리기 위해 삭제해야 하는 최소 문자 수를 구해라.

---

문자들의 빈도를 구한 뒤 배열에 저장해서 내림차순 정렬한다.

"aaaabccccd" -> [4, 4, 1, 1]

 

배열을 탐색하면서 가능한 최대 빈도수를 구한 뒤 이와 비교하여 삭제해야 하는 문자 수를 구한다.

초기 최대 빈도 수는 배열의 첫번째 원소와 같다.

가능 최대 빈도수는 파란색의 경우 "가능 최대 빈도 수 - 1"로 갱신된다.

빨간 색의 경우 "탐색 중인 빈도 수 - 1"로 갱신된다.

가능 최대 빈도 수는 위 두 가지 중 최소 값이다.

 

삭제 문자 수는 빈도 수 - 가능 최대 빈도 수 이거나 해당 값이 음수인 경우 0이다.

 

시간복잡도는 문자열 s의 길이를 N이라 할 때, O(NlogN).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1647.%20Minimum%20Deletions%20to%20Make%20Character%20Frequencies%20Unique.cpp