[백준 3017] 가까운 수 찾기

🔗 알고리즘 문제

단순 백트래킹 문제이지만, 백트래킹에서 필요없는 수는 제외하기 위한 그리디 조건을 생각해내는게 어려웠던 문제이다.

문제 분석

이 문제는 두 수 a와 b가 주어질 때 b를 재배치하여 만들 수 있는 수 중 a보다 크거나 같은 수 중 최소, a보다 작은 수 중 최대 수를 출력하는 문제이다.

a가 3022이고 b가 1232 일 때 b를 재배치하여 만들 수 있는 수는 다음과 같다.

1223, 1232, 1322, 2123, 2132, 2213, 2231, 2312, 2321, 3122, 3212, 3221

이 중 a보다 크거나 같은 수 중 최소 수는 3122이고, a보다 작은 수 중 최대 수는 2023이다.

만약 해당하는 수가 없을 경우에는 0을 출력한다.

발상 & 알고리즘 설계

b라는 수를 재배치하여 조건에 맞는 수를 구해야 하기에 백트래킹을 이용하였다.

void search(int cnt){
    if(cnt == n){
        if(check >= a){
            maxVal = check;
            cout << (maxVal.empty() ? "0" : maxVal) << "\n" << (minVal.empty() ? "0" : minVal);
            exit(0);
        }

        if(check[0] != '0' && check < a){
            minVal = check;
        }

        return;
    }

    char temp = ' ';

    for(int i = 0; i < n; i++){
        if(b[i] != temp && !visited[i]){
            check[cnt] = b[i];
            temp = b[i];
            visited[i] = true;
            search(cnt + 1);
            visited[i] = false;
        }
    }
}

처음에는 다음과 같이 단순 백트래킹과 if문을 이용해서 가장 가까운 수를 찾아주었다.

하지만 이렇게 될 경우 b를 이용해 만들 수 있는 모든 수를 찾아내서 비교하기에 b의 자릿수가 커지면 만들 수 있는 수의 갯수가 기하급수적으로 증가하여 시간초과가 나오게 되었다.

만들 수 있는 모든 수를 완전탐색하지 않고, 어떻게 가까운 수를 찾을 수 있을가를 고민하던 중 친구의 조언을 듣고 a보다 크거나 같은 수를 찾을 때는 현재 만들고 있는 수가 a보다 작으면 더 이상 탐색할 필요가 없다. 라는 힌트를 받게 되었다.

이 힌트를 바탕으로 a보다 크거나 같은 수를 찾는 함수, a보다 작은 수를 찾는 함수를 나누어, a보다 크거나 같은 수를 찾을 때는 만드는 중인 숫자가 a보다 작아지면 return a보다 작은 수를 찾을 때는 수가 a보다 크거나 같아지면 return하는 방식으로 완전탐색을 하지 않고도 가까운 수를 찾아낼 수 있었다.

코드

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

using namespace std;

string a;
string b;

int n;
bool complete = false;

char* check;
bool visited[60] = {};

void search1(int cnt){
    if(check < a)
        return;

    if(cnt == n){
        complete = true;
        return;
    }

    char temp = ' ';

    for(int i = 0; i < n; i++){
        if(b[i] != temp && !visited[i]){
            check[cnt] = b[i];
            temp = b[i];
            visited[i] = true;
            search1(cnt + 1);

            if(complete)
                break;

            visited[i] = false;
        }
    }
}

void search2(int cnt){
    if(check >= a)
        return;

    if(cnt == n){
        complete = true;
        return;
    }

    char temp = ' ';

    for(int i = 0; i < n; i++){
        if(!(cnt == 0 && b[i] == '0') && b[i] != temp && !visited[i]){
            check[cnt] = b[i];
            temp = b[i];
            visited[i] = true;
            search2(cnt + 1);

            if(complete)
                break;

            visited[i] = false;
        }
    }
}

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

    if(a == b){
        cout << b << "\n" << 0;
        return 0;
    }

    n = b.length();
    sort(b.begin(), b.end(), less<>());

    check = new char[n];
    fill(check, check + n, '9');
    search1(0);
    cout << (complete ? check : "0") << "\n";

    complete = false;
    sort(b.begin(), b.end(), greater<>());
    fill(check, check + n, '0');
    fill(visited, visited + n, false);
    search2(0);
    cout << (complete ? check : "0");
}