Minimum Deletions to Make String K-Special 문제 요약
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
데이터 분석
대상자
- 알고리즘 기초 학습자, 소프트웨어 개발 초보자
- 난이도: 중간 (정렬, 빈도 분석, 그리디 알고리즘 이해 필요)
핵심 요약
- 문제 목적: 문자열의 각 문자 빈도 차이를
k이하로 만드는 최소 삭제 횟수 계산 - 핵심 전략:
- 빈도 배열 정렬 후 그리디 스캔으로 최적 빈도 조합 탐색
freq[i]를 기준 빈도로 설정하고,freq[j]를freq[i] + k이하로 조정- 삭제 횟수 계산:
y - x - k(빈도 초과 시) 또는y(빈도 부족 시) - 시간 복잡도:
O(26^2)(상수 시간) - 공간 복잡도:
O(26)
섹션별 세부 요약
1. 문제 정의
- k-special 조건: 모든 문자의 빈도 차이가
k이하 - 목표:
word를 k-special하게 만들기 위한 최소 삭제 횟수 - 예:
word = "aabbcc", k = 1→a:2, b:2, c:2→ 조건 만족 (삭제 필요 없음)
2. 주요 관찰
- 빈도 계산: 각 문자의 빈도를
freq배열로 저장 - 그리디 전략:
freq[i]를 기준 빈도로 설정 →freq[j]를freq[i] + k이하로 조정freq[j] < freq[i]인 경우 해당 빈도의 문자는 전체 삭제
3. 알고리즘 구조
- 빈도 배열 정렬:
freq.sort()→ 빈도 기반 분석 용이 - 반복 처리:
i인덱스를 기준 빈도로 설정 (x = freq[i])j인덱스의 빈도(y)를x + k이하로 조정y - x > k→y - x - k삭제 횟수 누적y < x→y삭제 횟수 누적ans = min(ans, ops)로 최소 삭제 횟수 업데이트
4. 예시 코드 구현
- C++:
```cpp
int minimumDeletions(string word, int k) {
vector
for (char ch : word) freq[ch - 'a']++;
sort(freq.begin(), freq.end());
int ans = 1e5 + 5;
int i = 0;
while (freq[i] == 0) i++;
int t = i;
for (; i < 26; i++) {
int x = freq[i], ops = 0;
for (int j = t; j < 26; j++) {
if (i == j) continue;
int y = freq[j];
if (y - x > k) ops += y - x - k;
if (y < x) ops += y;
ans = min(ans, ops);
}
}
return ans;
}
```
- Python:
```python
def minimumDeletions(self, word: str, k: int) -> int:
freq = [0] * 26
for ch in word: freq[ord(ch) - ord('a')] += 1
freq.sort()
i = 0
while i < 26 and freq[i] == 0: i += 1
t = i
ans = float('inf')
for i in range(t, 26):
x = freq[i]
ops = 0
for j in range(t, 26):
if i == j: continue
y = freq[j]
if y - x > k: ops += y - x - k
if y < x: ops += y
ans = min(ans, ops)
return ans
```
결론
- 핵심 팁:
- 빈도 배열 정렬 후 기준 빈도 기반으로
k범위 내 조정 freq[i]를 기준으로 하되,freq[j]의 초과/부족을 모두 고려해야 함- Greedy 알고리즘과 빈도 분석의 조합이 핵심
k = 0일 경우, 모든 빈도가 동일해야 하므로 최대 빈도 기준으로 삭제 횟수 계산 가능