백준 16943 - 숫자 재배치

https://www.acmicpc.net/problem/16943

16943번: 숫자 재배치

입력으로 들어오는 정수 A를 숫자가 아니라, '0' 부터 '9' 까지의 문자가 들어오는 문자열로 보면

이 문자열 배열에 대해서 next_permutation 을 통해서

순서를 섞어낼 때의 모든 조합을 구할 수 있다.

 

모든 순서를 찾아보는 시간복잡도는 O(N!) 이고,

A는 10^9보다 작은 수이기 때문에 최대 9자리라서 N=9 이다.

이때의 계산 횟수는 대략 40만언저리쯤 된다.

 

int의 범위는 2,000,000,000 를 넘기 때문에,

N=9 인 이 문제의 모든 입력에 대해서 문자열을 섞을 때에도

섞인 문자열이 int 범위를 넘어가지 않음을 확인할 수 있다.

 

문자열로 봐서 모든 조합에 대해 탐색을 할 때,

섞인 문자열을 다시 숫자로 구성해서 B와 비교해서 정답을 갱신하는데,

섞인 문자열의 제일 앞자리 S[0] 이 '0' 인 경우는

C는 0으로 시작하면 안 된다.

지문에 의해서 계산해주면 안된다.

 

#include <bits/stdc++.h>
using namespace std;


char A[12];
int B;
int N;

int make_int(char* S, int len){
	int ans = 0;
	for(int i=0; i<len; i++){
		ans += (S[i]-'0') * pow(10,len-i-1);
	}
	return ans;
}

bool cmp(){
	int a = make_int(A,N);
	
	if(a<B) return true;
	else return false;
}

int main(){
	cin >> A >> B;
	
	N = strlen(A);
	sort(A, A+N);
	
	int ans = -1;
	do{
		if(A[0] == '0') continue;
		if(cmp()){
			ans = max(ans, make_int(A,N));
		}
	}while(next_permutation(A,A+N));
	
	cout << ans;
	return 0;
}