[백준 16943] 숫자 재배치(C++)

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

16943번: 숫자 재배치

문제

---

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

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

 

입력

---

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

 

출력

---

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

 

제한

---

• 1 ≤ A, B < 10⁹

 

^{문제 풀이}

---

백트래킹 문제.

A와 B를 입력받아 A의 각 자리수를 배열에 저장한 후, 백트래킹을 통해 A가 가진 숫자들로 만들 수 있는 모든 조합을 찾아낸다. (단, 첫 자리가 0인 경우 제외)

만들 수 있는 조합 중 C보다 작으면서 가장 큰 수를 찾아 출력한다.

 

아래는 코드.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string A, B;
int* arr;
int* answerArr;
bool* isVisited;
int maxAnswer = -1;

void backTracking(int depth, int maxDepth)
{
	if (depth == maxDepth)
	{
		int answer = 0;
		for (int i = 0; i < maxDepth; i++)
		{
			answer = answer * 10 + answerArr[i];
		}
		if (answer > maxAnswer && answer < stoi(B))
		{
			maxAnswer = answer;
		}
	}
	else
	{
		for (int i = 0; i < maxDepth; i++)
		{
			if (depth == 0 && arr[i] == 0)
			{
				continue;
			}
			if (isVisited[i] == false)
			{
				answerArr[depth] = arr[i];
				isVisited[i] = true;
				backTracking(depth + 1, maxDepth);
				isVisited[i] = false;
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> A >> B;
	int N = A.length();
	arr = new int[N];
	isVisited = new bool[N];
	answerArr = new int[N];
	for (int i = 0; i < N; i++)
	{
		arr[i] = A.at(i) - 48;
		isVisited[i] = false;
	}
	backTracking(0, N);
	cout << maxAnswer << "\n";
	return 0;
}