문제 개요
문자열이 하나 주어져 있고, 특정 문자의 모든 등장(occurrence)을 제거한 후 문자열에 남은 각 문자의 ASCII 값 합계를 최소화하는 것이 목표입니다. 예를 들어 "hello"라는 문자열이 주어지면 전체 ASCII 값의 합은 (104 + 101 + 108 + 108 + 111) = 532가 됩니다. 이제 각 문자별로 등장 횟수와 비용을 확인해 보겠습니다.
- h는 1번 등장하므로 비용은 1 × 104 = 104
- e는 1번 등장하므로 비용은 1 × 101 = 101
- l은 2번 등장하므로 비용은 2 × 108 = 216
- o는 1번 등장하므로 비용은 1 × 111 = 111
여기서 l이 가장 많이 등장했으므로, l의 모든 등장을 제거하면 합계가 가장 작아집니다. 다시 말해 위 목록에서 기여도가 가장 큰 값을 제거하는 것과 같습니다. 따라서 최종 결과는 532 − 216 = 316이 됩니다.
풀이 접근 방식
핵심 로직은 매우 단순합니다.
- 먼저 문자열 전체의 ASCII 값 총합을 구합니다.
- 문자열에 등장하는 각 문자의 빈도(frequency)를 계산합니다.
- (등장 횟수 × ASCII 값)으로 계산되는 기여도가 가장 큰 문자를 찾아 제거 대상으로 삼습니다.
- 전체 합에서 해당 기여도를 뺀 값이 곧 최소화된 결과입니다.
이 알고리즘의 시간 복잡도는 문자열을 한 번 순회하므로 O(n)이며, 알파벳 소문자만 다루는 경우 빈도 배열의 크기가 26으로 고정되어 공간 복잡도는 O(1)입니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int minASCIISum(string str, int len) {
int max_val = INT_MIN, sum = 0;
int frequency[26] = { 0 };
for (int i = 0; i < len; i++) {
frequency[str[i] - 'a']++;
sum += (int)str[i];
}
for (int i = 0; i < 26; i++)
max_val = max(max_val, frequency[i] * (i + 'a'));
return (sum - max_val);
}
int main() {
string str = "hello";
int n = str.length();
cout << "Minimized Sum: " << minASCIISum(str, n);
}실행 결과
Minimized Sum: 316