코드 포스(Code Force) 915 - C. Permute Digits

문제 유형: 그리디

문제 URL: https://codeforces.com/contest/915/problem/C

  이 문제는 특정한 수가 주어졌을 때 그 수로 순열을 처리하는 문제입니다. 두 수 a와 b가 있다고 합시다. 이 때 a로 만들 수 있는 자릿수의 순열 중에서 b보다 크지 않은 가장 큰 수를 구해 출력하는 문제입니다. 입력과 출력으로는 0으로 시작하지 않는 양의 정수가 입력 됩니다. 이 때 자릿수의 순열이란, 수에서 숫자들의 자리를 서로 바꾸어 나타낼 수 있는 수들을 의미합니다.

  b보다 크지 않은 가장 큰 수를 구해야 하므로 맨 왼쪽부터 가장 큰 숫자가 나올 수 있도록 하나씩 숫자를 배정하면 문제를 해결할 수 있습니다. 이 때 가장 중요한 것은 단순히 들어갈 수 있는 가장 큰 숫자를 넣는다고 되지는 않습니다. 그렇게 하면 답을 못 구할 수도 있어요. 숫자를 하나씩 넣을 때마다 최소 크기 접미사를 붙여서 b보다 작은지 검사하는 로직이 추가적으로 필요합니다.

  a: 123456789123456789

  b: 276193619183618162

  왜 최소 크기 접미사를 구해야 하는지는 위의 예시를 통해 확인할 수 있습니다.

  단순히 들어갈 수 있는 가장 큰 숫자를 계속해서 배정하면 '276193619'에서 더이상 진행할 수 없습니다. 그 뒤에 오는 b의 숫자가 1이므로, 문자열 a에 포함된 숫자 중에서 넣을 수 있는 1보다 작거나 같은 숫자는 더 이상 존재하지 않기 때문이에요. 그러므로 9 대신 그 다음 작은 숫자인 8이 들어가서 '2761936189~'로 진행되는 방식으로 처리해야 합니다. 이를 효과적으로 판단하기 위해서 최소 크기 접미사를 넣어보는 겁니다.

  9를 넣는 경우와 8을 넣는 경우를 비교해봅시다. 왼쪽의 수는 우리가 찾을 해답이고, 오른쪽에 있는 수는 b를 의미합니다.

  276193619234455788 > 276193619183618162 (불가능)

  276193618234455789 < 276193619183618162 (가능)

  9를 넣는 경우와 8을 넣는 경우 각각에 대해서 최소 접미사를 붙인 경우는 위와 같습니다. 9가 들어가는 경우에는 최소 크기 접미사를 붙였을 때, b보다 더 커지므로 불가능한 것입니다. 반면에 그보다 더 작은 숫자인 8부터 다시 넣어서 최소 크기 접미사를 붙여보니 b보다 작거나 같으므로 8은 들어갈 수 있는 것입니다. 결과적으로 기본적으로 왼쪽부터 최대한 큰 숫자를 채워 넣고, 해당 숫자가 들어갈 수 있는 지의 여부는 최소 접미사를 통해 확인할 수 있는 것입니다.

※ 예제 입출력 ※

input

Copy

123
222

output

Copy

213

input

Copy

3921
10000

output

Copy

9321

input

Copy

4940
5000

output

Copy

4940

※ 정답 소스코드 ※

(컴파일 환경: GNU G++11 5.1.0)

#include <iostream>
#define MAX 10

using namespace std;

string a, b;
int d[MAX];
string res;

// 남은 뒷 자릿들을 '가장 작은 수'가 되도록 채웁니다. 
void makeSmall(int from)
{
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < d[i]; j++)
			res[from++] = i + '0';
}

int main()
{
	cin >> a;
	cin >> b;
	for (int i = 0; i < a.length(); i++)
		d[a[i] - '0']++;
	int zeros = 0;
	// A가 B보다 자릿수가 작은 경우 앞에 0을 채웁니다. 
	while (a.length() < b.length()) {
		a = "0" + a;
		zeros++;
	}
	res = a;
	// '원래 A의 길이'만큼 반복합니다. 
	for (int i = zeros; i < a.length(); i++) {
		// 9부터 0까지의 숫자 중에서 들어갈 수 있는 것을 고릅니다. 
		for (int j = MAX - 1; j >= 0; j--) {
			// 일단 넣어 봅니다. 
			if (d[j] > 0) {
				d[j]--;
				res[i] = j + '0';
				// 현재 넣은 숫자를 토대로 뒷자리들은 최대한 작게 구성합니다.
				// 이렇게 만들어진 수가 가능한 수라면 break;하여 해당 자릿수 구성을 완료합니다. 
				makeSmall(i + 1);
				cout << i << ":" << res << '\n';
				if (res <= b) break;
				d[j]++;
			}	
		}
	}
	// 앞에 들어가는 0은 무시하고 출력합니다. 
	int pos = 0;
	while (res[pos] == '0') pos++;
	cout << res.substr(pos);
	return 0;
}