이 튜토리얼에서는 길이 N의 숫자를 변환하여 임의의 한 자릿수가 최소 'K'번 이상 포함되도록 만드는 프로그램을 C++로 구현하는 방법을 살펴봅니다.
문제 개요
길이 N의 숫자 문자열이 하나 주어집니다. 우리가 해야 할 일은 주어진 숫자의 일부 자릿수를 변경하여, 어떤 한 자릿수든 최소 'K'번 이상 반복되도록 만드는 것입니다. 이때 자릿수 하나를 변경하는 비용은 원래 값과 새로운 값 사이의 절대 차이로 정의되며, 모든 변경 비용의 합을 계산한 뒤 그중 최소 비용과 함께 변환된 숫자를 출력해야 합니다.
접근 방식
이 문제는 다음과 같은 절차로 해결할 수 있습니다.
- 0부터 9까지의 모든 자릿수를 차례로 목표(target) 자릿수로 지정합니다.
- 각 목표 자릿수마다 원래 숫자에 이미 포함된 해당 자릿수의 개수를 먼저 셉니다.
- 변경 비용이 가장 작은 자릿수, 즉 목표 자릿수와의 거리가 가까운 자릿수부터 우선적으로 변경하며, 목표 자릿수의 개수가 K에 도달할 때까지 반복합니다.
- 증가 방향(작은 수를 큰 수로) 변경은 왼쪽에서 오른쪽으로, 감소 방향 변경은 오른쪽에서 왼쪽으로 탐색합니다.
- 열 가지 목표 자릿수 각각에 대해 얻은 (비용, 결과 문자열) 쌍 중 비용이 가장 작은 것을 최종 답으로 선택합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 최솟값과 최종 숫자를 계산하는 함수
int get_final(int n, int k, string a){
int modtemp;
// 목표 자릿수로 변경된 숫자의 개수
int co;
string temp;
// 최소 비용 저장
pair<int, string> ans = make_pair(INT_MAX, "");
for (int i = 0; i < 10; i++) {
temp = a;
// 임시로 수정된 숫자 저장
modtemp = 0;
co = count(a.begin(), a.end(), i + '0');
for (int j = 1; j < 10; j++) {
if (i + j < 10) {
for (int p = 0; p < n; p++) {
if (co <= k)
break;
if (i + '0' == temp[p] - j) {
temp[p] = i + '0';
modtemp += j;
co++;
}
}
}
if (i - j >= 0) {
for (int p = n - 1; p >= 0; p--) {
if (co >= k)
break;
if (i + '0' == temp[p] + j) {
temp[p] = i + '0';
modtemp += j;
co++;
}
}
}
}
// 기존 최소 비용보다 작으면 교체
ans = min(ans, make_pair(modtemp, temp));
}
cout << ans.first << endl << ans.second << endl;
}
int main(){
int n = 5, k = 4;
string a = "21122";
get_final(n, k, a);
return 0;
}
출력 결과
1 21222
코드 설명
예제의 입력은 N=5, K=4, 숫자 문자열 "21122"입니다. 두 번째 자릿수 '1'을 '2'로 딱 한 번만 바꾸면 '2'가 네 개가 되어 조건을 만족하므로, 최소 비용 1과 변환된 숫자 "21222"가 출력됩니다.
get_final 함수는 0부터 9까지의 각 자릿수를 목표로 삼아 필요한 변경을 수행한 뒤, pair<int, string> 형태로 비용과 결과 문자열을 함께 보관합니다. 이렇게 하면 min 함수를 통해 비용을 기준으로 손쉽게 비교할 수 있어, 최적의 변환 결과를 깔끔하게 얻을 수 있습니다.