16943 숫자 재배치

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

16943번: 숫자 재배치

숫자 재배치

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

619

296

218

45.228%

문제

두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 

가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

B보다 작거나 같은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.

제한

• 1 ≤ A, B < 10^9

 

 

풀이)
9자리 수이므로 순열을 사용하여 푼다. 9! (9팩토리얼 시간복잡도)

 

1. 시작인 0인지 잘 체크한다.

 

2. 순열을 이용한 문자들을 스택을 이용하여 숫자로 만듦

 

3. 나머지는 그냥 구현

 

#include<iostream>
#include<algorithm>
#include<string>
#include<stack>

using namespace std;

int main(void)
{
	int a, b;
	cin >> a >> b;

	string A = to_string(a);
	sort(A.begin(),A.end());

	int num = 0;
	int ans = -1;
	stack<int> before;
	do
	{
		int sum = 0;
		stack<int> s;
		bool isStart_zero = false;
		for (int i = 0; i < A.length(); ++i)
		{
			if (A[0] - '0' == 0)
			{
				isStart_zero = true;
				break;
			}
			s.push(A[i] - '0');
		}
		if (isStart_zero) continue;

		for(int i=0,start=1; i<A.length();i++,start*=10)
		{
			num = s.top();
			num *= start;
			sum += num;
			s.pop();
		}
		if (sum <= b)
		{
			ans = max(ans, sum);
		}
	} while (next_permutation(A.begin(), A.end()));
	
	cout << ans << '\n';
	return 0;