[2992번] 크면서 작은 수

www.acmicpc.net/problem/2992

2992번: 크면서 작은 수

 

 

두가지 풀이를 가지고 왔습니다.

 

1. 첫번째는 풀이는 강의에서 소개해주신 next_permutation 함수를 이용하는 방식입니다.

 

코드가 매우 직관적이고 간결합니다.

string변수로 입력을 받고난뒤 next_permutation 함수를 1번 실행시키면

문제에서 요구하는 "크면서 작은 수"를 얻을 수 있습니다. 

if 조건문 내부에서 next_permutation 함수를 실행시킴으로서 정답이 없는 경우에 대해 예외처리를 합니다.

( 다음 순열이 없는 경우 next_permutation 함수는 false 를 return 합니다. )

전체코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {

	string x; cin >> x;
    
	if (next_permutation(x.begin(), x.end())) 
		cout << x << endl;
	else
		cout << 0 << endl;
	
	return 0;
}

2. 두번째 풀이는 백트래킹을 이용한 방식입니다.

 

개인적으로 백트래킹을 이해하는데 정말 고생을 했는데

해당 문제를 백트래킹으로 구현하려고 고민하던 과정에서 이해하는데 큰 도움이 되었습니다.

 

읽어보면 이해가 될 법한 부분은 주석으로 처리해 두었습니다.

 

저처럼 재귀함수에 익숙하지 않은 상태에서 백트래킹을 처음 접하신분들은 

백트래킹 함수를 구현하면서 고민 많이 하셨을 것 같습니다.

 

함수 부분을 살펴보겠습니다.

void func(int cnt) {

	// 재귀 호출 종료 조건
	if (cnt == v.size()) {

		int value = vector_to_int(temp);
		if ((value > x) && !is_answer) {
			is_answer = true;
			cout << value;
		}

		return;
	}

	for (int i = 0; i < v.size(); i++) {
		if (!is_used[i]) {

			is_used[i] = true;
			temp.push_back(v[i]);

			func(cnt + 1);

			if (is_answer) return;

			is_used[i] = false;
			temp.pop_back();

		}
	}

}

우선 재귀함수의 가장 중요한 종료조건을 먼저 선언을 합니다. 

v라는 vector에는 입력 받은 수의 각 자리수가 오름차순으로 정렬되어 저장이 돼있습니다. (main함수에서 처리)

따라서 v.size() 는 입력 받은 수의 총 자리수에 해당합니다.

[  ex)   x=1546 일 떄,  v = {1,4,5,6}  ,  v.size() = 4   ]

 

func 함수는 한 번 호출이 될 때 마다, v 에서 숫자 하나를 결과 배열 temp 에 추가합니다. (temp는 전역변수로 선언되어있습니다.)

즉 func(0), func(1), ... , func(cnt) 순서로 재귀적으로 호출이 되다가  cnt == v.size() 가 되는 순간에는 v에 있는 모든 숫자를 한번씩 결과 배열 temp 에 추가한 상태입니다.

 

종료조건을 만족했을 떄 결과배열 temp를 이용해서 입력받은 x와 크기를 비교합니다.

오름차순으로 정렬된 v 를 이용해서 만든 결과값 임으로, x보다 결과값이 커지는 순간 정답이 됩니다.

 

정답을 찾은 이후에 호출되어있는 재귀 함수들은 의미가 없으므로 is_answer 이라는 bool 타입 변수를 이용해서 모든 재귀 호출을 return합니다.

 

다음으로는 for문을 보겠습니다.

v의 각 원소에 매치되는 bool 타입 is_used라는 선언해서 이미 사용한 원소인지 판별 후에 

사용하지 않은 원소라면 결과 배열 temp에 추가하고 다음 재귀 호출 func(cnt + 1)을 수행합니다.

 

종료조건에 도달한 뒤 재귀 호출이 종료되면 is_used를 다시 false로 돌려놓고

결과 배열 temp에서도 해당 원소를 pop_back 해줍니다.

전체코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// BackTracking을 위한 전역변수 선언
int x;
vector<int> v;
vector<int> temp;
vector<bool> is_used;
bool is_answer;

int vector_to_int(const vector<int>& vec) {
	int result = 0;
	for (auto num : vec) {
		result = result * 10 + num;
	}
	return result;
}

void func(int cnt) {

	// 재귀 호출 종료 조건
	if (cnt == v.size()) {

		int value = vector_to_int(temp);
		if ((value > x) && !is_answer) {
			is_answer = true;
			cout << value;
		}

		return;
	}

	for (int i = 0; i < v.size(); i++) {
		if (!is_used[i]) {

			is_used[i] = true;
			temp.push_back(v[i]);

			func(cnt + 1);

			if (is_answer) return;

			is_used[i] = false;
			temp.pop_back();

		}
	}

}

int main() {

	ios::sync_with_stdio(false); cin.tie(NULL);

	// 입력 받기
	cin >> x;
	int tmp = x;

	// 입력 받은 [int형 변수 x] 를 [vector<int>형 변수 v]에 한 자리씩 저장
	while (tmp) {
		v.push_back(tmp % 10);
		tmp /= 10;
	}
	sort(v.begin(), v.end());	// 오름차순으로 정렬

	for (int i = 0; i < v.size(); i++)	is_used.push_back(false);	// is_used 변수 초기화

	func(0);	// back tracking 함수 호출
	if (!is_answer) cout << 0;	// 정답이 없는 경우 0 출력

	return 0;
}