[2992번] 크면서 작은 수
2992번: 크면서 작은 수
정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이
www.acmicpc.net
두가지 풀이를 가지고 왔습니다.
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;
}