[백준 2992] 크면서 작은 수 (C++)

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

 

문제

---

정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다.

수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 같다. 하지만, 123과 432는 구성이 같지 않다.

 

입력

---

첫째 줄에 X가 주어진다. (1 ≤ X ≤ 999999) X는 0으로 시작하지 않는다.

 

출력

---

 

첫째 줄에 결과를 출력한다. 만약 그러한 숫자가 없는 경우에는 0을 출력한다.

 

문제 풀이

---

백트래킹 문제.

입력 받은 숫자의 배치를 섞어서 입력 받은 숫자보다 크면서 만들 수 있는 가장 작은 수를 찾아야 한다. 입력을 문자열로 받아 각 자리의 수를 배열에 저장해두고, 해당 자리의 수를 아직 사용하지 않았다면 문자열에 붙여가는 방식으로 백트래킹으로 만들 수 있는 모든 경우를 찾는다.

백트래킹 함수의 깊이가 입력 받은 숫자의 자리수만큼 도달했다면 순서가 섞인 문자열이 완성된 것이다. 입력 문자열과 비교하여 더 크면서 가장 작은 수를 저장한다.

 

또는 next_permutation()으로 답을 바로 구할 수 있다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <string>
#define INF 987654321
using namespace std;
string str;
char* answerArr;
char* inputArr;
int answer = INF;
bool* isVisited;
int N;

void backTracking(int depth)
{
	if (depth == N)
	{
		string currentStr = "";
		for (int i = 0; i < N; i++)
		{
			currentStr += answerArr[i];
		}
		int currentInt = stoi(currentStr);
		if (currentInt > stoi(str) && currentInt < answer)
		{
			answer = currentInt;
		}
	}
	else
	{
		for (int i = 0; i < N; i++)
		{
			if (isVisited[i] == false)
			{
				answerArr[depth] = inputArr[i];
				isVisited[i] = true;
				backTracking(depth + 1);
				isVisited[i] = false;
			}
		}
	}
}

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

	cin >> str;
	N = str.length();
	isVisited = new bool[N];
	inputArr = new char[N];
	answerArr = new char[N];
	for (int i = 0; i < N; i++)
	{
		inputArr[i] = str.at(i);
		isVisited[i] = false;
	}
	backTracking(0);
	if (answer == INF)
	{
		cout << 0 << "\n";
	}
	else
	{
		cout << answer << "\n";
	}
	return 0;
}