알고리즘 문제/Leetcode
[Leetcode] 1647. Minimum Deletions to Make Character Frequencies Unique
햄과함께
2022. 6. 28. 18:57
320x100
문제 : 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).
320x100