[BOJ / C++] 백준 2529 부등호

문제

https://www.acmicpc.net/problem/2529

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

---

풀이

1. 순열을 이용한 풀이 (브루트 포스)

2. 백트래킹을 이용한 풀이

 

1번 풀이

처음에는 0~9까지 k+1개만큼 수를 뽑고 순열로 만든 수를 사용하여 브루트포스로 풀어봤다.

이때 string 형태로 뽑은 수를 바꾸고, 비교할 때는 long long 타입으로 수를 바꿔서 max 함수로 비교했는데

그 과정에서 문제가 있었다. 그래서 string 자체를 사용하여 최대, 최소값을 갱신했다.

#include <bits/stdc++.h>

using namespace std;
int k;
string ans_max = "0";
string ans_min = "9999999999";
vector<char> v(10, 0);

void check(string num) {
    bool flag = true;
    for (int i = 0; i < k; i++) {
        if (!flag) {
            return;
        }
        switch (v[i]) {
        case '<':
            if (num[i] >= num[i + 1]) {
                flag = false;
            }
            break;
        case '>':
            if (num[i] <= num[i + 1]) {
                flag = false;
            }
            break;
        }
    }

    if (flag) {
        ans_max = max(ans_max, num);
        ans_min = min(ans_min, num);
    }
}

int main() {
    cin >> k;
    vector<int> arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

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

    vector<int> sub_arr(arr.size(), 1);
    for (int i = 0; i < k + 1; i++) {
        sub_arr[i] = 0;
    }

    do {
        string temp;
        for (int i = 0; i < arr.size(); i++) {
            if (sub_arr[i] == 0) {
                temp += to_string(arr[i]);
            }
        }

        do {
            string temp2;
            for (int i = 0; i < temp.size(); i++) {
                temp2.push_back(temp[i]);
            }

            check(temp2);
        } while (next_permutation(temp.begin(), temp.end()));

    } while (next_permutation(sub_arr.begin(), sub_arr.end()));

    cout << ans_max << "\n" << ans_min;

    return 0;
}

 

2번 풀이

모든 경로를 구하는 것처럼 백트래킹을 사용하여 k+1 자리 수를 만들 수 있다.

수를 뽑을 때마다 부등호 조건을 만족하는지 확인하고, 만족하지 않는다면 넘어가는 구조로 시간을 줄일 수 있다.

2번 풀이에서 시간을 4ms로 단축할 수 있었다. 

 

#include <bits/stdc++.h>

using namespace std;
int k;
string ans_max = "0";
string ans_min = "9999999999";
vector<char> v(10, 0);
vector<int> is_used(10, 0);
vector<int> picked;

void update() {
    string temp;
    for (auto n : picked) {
        temp += to_string(n);
    }
    ans_max = max(ans_max, temp);
    ans_min = min(ans_min, temp);
}
void backTracking(int idx) {
    if (idx > k) {
        update();
        return;
    }

    for (int i = 0; i < 10; i++) {
   		// 이미 사용한 수 (i)는 제외
        if (is_used[i]) {
            continue;
        }
        // 부등호 조건 만족하지 않으면 제외
        if (v[idx - 1] == '<' && picked[idx - 1] > i) {
            continue;
        } else if (v[idx - 1] == '>' && picked[idx - 1] < i) {
            continue;
        }
		
        // 사용처리 및 추가
        is_used[i] = 1;
        picked.push_back(i);
        
       	// 추가로 뽑기
        backTracking(idx + 1);
        
        // 원복
        is_used[i] = 0;
        picked.pop_back();
    }
}

int main() {
    cin >> k;

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

    cout << ans_max << "\n" << ans_min;
    return 0;
}