[BOJ_2529][Backtracking]부등호

부등호를 입력받으면 그 사이에 들어갈 수들을 붙여놓은 것 중 가장 큰 수와 작은 수를 찾아내는 문제입니다.

 

---

 

처음에 접근한 방식은 모든 경우의 수를 찾고 부등호에 대한 조건은 모든 수를 선택한 후에 알아보도록 하는 것이었습니다. 보통 재귀를 설계하는 방식처럼 final condition을 먼저 명시하였고, 이후에는 0에서 9까지의 반복문 안에서 check 배열을 넣었다가 풀며 재귀를 돌렸습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

/* 부등호 */
using namespace std;

char a[15], check[15];
int k;
vector<string> ans; 

string to_string(int i) {
    char j = i + '0';
    string k = "";
    k.push_back(j);
    return k;
}

bool compare_condition(string num) {
    int cnt = 0;
    for (int i = 0; i < sizeof(a); i++) {
        if (a[i] == '<') {
            if (!(num[i] < num[i + 1])) return false;
        }
        if (a[i] == '>') {
            if (!(num[i] > num[i + 1])) return false;
        }
    }

    return true;
}

void go(int cnt, string num) {
    // final 
    if (cnt == k + 1) {
        if (compare_condition(num)) {
            ans.push_back(num);
        }
        return;
    }
    
    for (int i = 0; i <= 9; i++) {
        if (check[i]) continue;
        check[i] = true;
        go(cnt + 1, num + to_string(i));
        check[i] = false;
    }
   
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    cin >> k;

    for (int i = 0; i < k; i++) {
        cin >> a[i];
    } 

    go(0, "");
    sort(ans.begin(), ans.end());

    cout << ans.back() << '\n' << ans.front() << '\n';
}

 

위 방식으로 코드를 돌리면 답은 나오지만, VS로 답을 내기까지 10초 넘게 걸렸습니다.

< > < 이 들어왔을 때 3 2 5 4 가 생성된 경우를 생각해보면 3 < 2 > 5 < 4 로 처음부터 조건을 틀리게 되어 계산하는 의미가 없습니다. 위 코드는 이 부분을 모두 재귀적으로 계산하여 마지막에 값을 거르게 됩니다.

이런 경우는 계산을 하며 중간에 오답을 거르는 로직을 생각해 볼 수 있습니다. 이 방법으로는 시간복잡도와 직접적으로 연결된 재귀의 호출 횟수를 획기적으로 줄일 수 있습니다.

 

1. 재귀문 안에서 루프를 돌리며 첫 숫자라 이전 숫자가 존재하지 않는 상태이거나, 부등호 조건을 만족하는 경우, 지금 사용한 번호가 사용되지 않았었다면 다음 단계 호출.
2. 0부터 시작한 인덱스의 숫자가 k + 1 까지 다다랐다면, 조건에 맞는 숫자가 찾아졌으므로 벡터에 삽입.
3. 벡터 정렬 후 가장 앞 숫자와 마지막 숫자 출력

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

/* 부등호 */
using namespace std;

char a[15], check[15];
int k;
vector<string> ans;

string conv_to_string(int i) {
    char j = i + '0';
    string k = "";
    k.push_back(j);
    return k;
}

bool compare_condition(char m, char n, char ineq) {
    if (ineq == '<') {
        if (!(m < n)) return false;
    }
    else if (ineq == '>') {
        if (!(m > n)) return false;
    }
    return true;
}

void go(int cnt, string num) {
    // final 
    if (cnt == k + 1) {
        ans.push_back(num);
        return;
    }

    for (int i = 0; i <= 9; i++) {
        if (check[i]) continue;
        if (cnt == 0 || compare_condition(num[cnt - 1], i + '0', a[cnt - 1])) {
            check[i] = true;
            go(cnt + 1, num + conv_to_string(i));
            check[i] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    cin >> k;

    for (int i = 0; i < k; i++) {
        cin >> a[i];
    } 

    go(0, "");
    sort(ans.begin(), ans.end());

    cout << ans.back() << '\n' << ans.front() << '\n';
}

 

백트래킹 문제는 문제마다 시간을 줄일 수 있는 방법이 다르고, 이 문제 또한 문제에 맞게 가지를 치는 방식에 대한 발상과 설계가 중요한 문제였습니다.