N자리 숫자가 주어지고, 0부터 9까지 각 자릿수에 대한 대체 값을 담고 있는 배열이 함께 제공됩니다. 이때 연속된 하나의 구간만 딱 한 번 대체할 수 있다는 조건 하에서, 주어진 수를 최대한 크게 만드는 것이 이 문제의 목표입니다.
예제 입력 및 출력
예제 1
입력
N=1234, arr[]={3, 0, 1, 5, 7, 7, 8, 2, 9, 4}출력
1257
설명
- 숫자 3은 대체 값 5(arr[3])로 교체됩니다.
- 숫자 4는 대체 값 7(arr[4])로 교체됩니다.
두 자릿수는 서로 인접해 있으므로, 단 한 번의 구간 대체만으로 1234를 1257로 만들 수 있습니다.
예제 2
입력
N=5183, arr[]={3, 0, 1, 5, 7, 7, 8, 2, 9, 4}출력
7183
설명
맨 앞자리 5는 대체 값 7(arr[5])로 커질 수 있습니다. 그러나 그다음 자릿수 1의 대체 값은 0(arr[1])으로 오히려 작아지기 때문에, 대체 구간은 첫 번째 자릿수에서 멈춥니다.
접근 방식 (그리디 알고리즘)
이 문제는 그리디(Greedy) 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 왼쪽(높은 자릿값)에서 오른쪽으로 탐색하면서, 대체 값이 원래 값보다 큰 첫 번째 자릿수를 찾습니다.
- 그 자릿수부터 대체를 시작합니다. 대체를 시작하는 위치가 앞쪽일수록 숫자 전체의 가치가 더 크게 올라가기 때문입니다.
- 이후 자릿수들이 계속해서 대체 값이 원래 값보다 크거나 같은 동안 교체를 진행합니다.
- 대체 값이 오히려 작아지는 자릿수를 만나면 즉시 대체를 중단하고 결과를 반환합니다. 한 번의 대체 기회를 소진했기 때문에 더 이상 교체할 수 없습니다.
이 방식이 최적인 이유는, 대체 기회가 단 한 번뿐이므로 가장 왼쪽에서 시작해 가능한 한 많은 자릿수를 키우는 것이 항상 가장 큰 수를 만들기 때문입니다.
구현 예제 (C++)
#include <bits/stdc++.h>
using namespace std;
string Max(string str, int arr[]) {
int N = str.size();
// 문자열 끝까지 탐색
for (int i = 0; i < N; i++) {
// 대체 값이 현재 자릿수보다 큰지 확인
if (str[i] - '0' < arr[str[i] - '0']) {
int j = i;
// 대체 값이 작아지기 전까지 계속 교체
while (j < N && (str[j] - '0' <= arr[str[j] - '0'])) {
str[j] = '0' + arr[str[j] - '0'];
j++;
}
return str;
}
}
// 변경할 곳이 없으면 원본 그대로 반환
return str;
}
// 메인 함수
int main() {
string str = "2075";
int arr[] = {3, 0, 1, 5, 7, 7, 8, 2, 9, 4};
cout << "주어진 수를 자릿수 구간 대체로 최대화한 결과: " << Max(str, arr);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
주어진 수를 자릿수 구간 대체로 최대화한 결과: 2375
동작 과정 상세 분석
입력이 2075이고 배열이 {3, 0, 1, 5, 7, 7, 8, 2, 9, 4}인 경우를 살펴보겠습니다.
- 첫 번째 자릿수 2의 대체 값은 1(arr[2])로 작으므로 건너뜁니다.
- 두 번째 자릿수 0의 대체 값은 3(arr[0])으로 더 크므로, 여기서 대체를 시작합니다.
- 0은 3으로 교체되지만, 세 번째 자릿수 7의 대체 값은 2(arr[7])로 작아지므로 대체가 여기서 중단됩니다.
- 최종 결과는 2375가 됩니다.
시간 복잡도
각 자릿수를 최대 두 번(탐색 시 한 번, 대체 시 한 번) 확인하므로, 시간 복잡도는 O(N)입니다. 여기서 N은 숫자의 자릿수 개수입니다. 공간 복잡도 역시 추가 배열 없이 문자열 자체를 수정하므로 O(1)입니다.