[백준] 2529번 : 부등호

문제

 

---

풀이

 

0~9까지의 숫자를 1번씩만 쓸 수 있기 때문에 visited로 관리할 수 있다.

부등호에 따라 숫자를 넣으며 백트래킹하면 되는데 나중에 stoi를 쓰기 위해 string 변수에 답을 쌓아놓는다.

---

소스코드

 

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

using namespace std;

vector<char> sign;
bool visited[10];
int k;
long long min_num = 9876543211, max_num = 0;

void backtracking(int pos, string str) {
    if (pos == k) { //부등호 다 쓰면 최대 최소 갱신
        long long result = stol(str);
        min_num = min(min_num, result);
        max_num = max(max_num, result);
        return;
    }

    string saved = str; //unvisited 처리용 기존 str
    for (int i = 0; i < 10; i++) {
        if (!visited[i]) {
            int last_num = str[str.size() - 1] - '0'; //str의 마지막 원소
            visited[i] = true; //visited 처리
            str += to_string(i);
            if ((sign[pos] == '<') && (last_num < i)) //부등호가 '<'이고 i가 last_num 보다 클 때
                backtracking(pos + 1, str);
            else if ((sign[pos] == '>') && (last_num > i)) //부등호가 '>'이고 i가 last_num 보다 작을 때
                backtracking(pos + 1, str);
            visited[i] = false; //unvisited 처리
            str = saved;
        }
    }
}

int main() {
    char input;

    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> input;
        sign.push_back(input);
    }
    for (int i = 0; i < 10; i++) { //첫번째 숫자 지정
        visited[i] = true;
        backtracking(0, to_string(i));
        visited[i] = false;
    }
    if (to_string(max_num).size() == k) //첫 자리가 0이면
        cout << 0;
    cout << max_num << '\n';
    if (to_string(min_num).size() == k) //첫 자리가 0이면
        cout << 0;
    cout << min_num << '\n';
}

전체 소스코드다.

 

    for (int i = 0; i < 10; i++) { //첫번째 숫자 지정
        visited[i] = true;
        backtracking(0, to_string(i));
        visited[i] = false;
    }

0부터 9까지 첫번째로 들어갈 숫자를 넣는다.

 

void backtracking(int pos, string str) {
    if (pos == k) { //부등호 다 쓰면 최대 최소 갱신
        long long result = stol(str);
        min_num = min(min_num, result);
        max_num = max(max_num, result);
        return;
    }

    string saved = str; //unvisited 처리용 기존 str
    for (int i = 0; i < 10; i++) {
        if (!visited[i]) {
            int last_num = str[str.size() - 1] - '0'; //str의 마지막 원소
            visited[i] = true; //visited 처리
            str += to_string(i);
            if ((sign[pos] == '<') && (last_num < i)) //부등호가 '<'이고 i가 last_num 보다 클 때
                backtracking(pos + 1, str);
            else if ((sign[pos] == '>') && (last_num > i)) //부등호가 '>'이고 i가 last_num 보다 작을 때
                backtracking(pos + 1, str);
            visited[i] = false; //unvisited 처리
            str = saved;
        }
    }
}

백트래킹 함수다.

 

    string saved = str; //unvisited 처리용 기존 str
    for (int i = 0; i < 10; i++) {
        if (!visited[i]) {
            int last_num = str[str.size() - 1] - '0'; //str의 마지막 원소
            visited[i] = true; //visited 처리
            str += to_string(i);
            if ((sign[pos] == '<') && (last_num < i)) //부등호가 '<'이고 i가 last_num 보다 클 때
                backtracking(pos + 1, str);
            else if ((sign[pos] == '>') && (last_num > i)) //부등호가 '>'이고 i가 last_num 보다 작을 때
                backtracking(pos + 1, str);
            visited[i] = false; //unvisited 처리
            str = saved;
        }
    }

나중에 unvisited 처리를 하기 위해 일단 기존의 str을 저장해둔다.

만약 visited 하지 않은 원소를 찾으면 일단 visited 처리를 하고 str에도 넣어둔다.

그리고 나서 부등호가 '<'였는지 '>'였는지 비교한다. 만약 promising하면 그대로 백트래킹 함수를 호출하지만

그렇지 않다면 다시 unvisited 처리한다.

 

    if (pos == k) { //부등호 다 쓰면 최대 최소 갱신
        long long result = stol(str);
        min_num = min(min_num, result);
        max_num = max(max_num, result);
        return;
    }

부등호를 다 사용하면 최댓값과 최솟값을 갱신한다.

 

    if (to_string(max_num).size() == k) //첫 자리가 0이면
        cout << 0;
    cout << max_num << '\n';
    if (to_string(min_num).size() == k) //첫 자리가 0이면
        cout << 0;
    cout << min_num << '\n';

마지막으로 출력을 하는데 만약 최댓값 또는 최솟값의 길이가 부등호의 수와 같다면 첫 자리가 0이라는 뜻이다.

그럴 경우엔 앞에 0을 출력해놓는다.