BOJ 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인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.

[입력] 
2
< > 

[출력] 
897
021

---

1. 문제 해석

어떤 문제에서 모든 방법들을 다 해봐야하는데 순서를 사용할 수 있다면, 그 문제는 순열을 이용하여 풀이할 수 있다.

우선, 문제에서 부등호의 개수가 k개이면 들어갈 수 있는 정수의 개수는 k+1개이다. 그리고 k+1개의 자리에 0~9의 서로 다른 정수가 들어가야 한다. 이때 부등호를 만족시키는 최대/최소의 수를 구하는 문제이다.

이 문제는 정수의 순서에 따라 답이 달라지게 되므로, 순서와 관련된 문제이다. 따라서 순열로 풀 수가 있다.

• 부등호 기호 < 와 > 가 나열된 수열 A가 있다.
• 기호의 앞뒤에 한 자리 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다.
• 이때, 선택된 수는 모두 달라야 한다.
• k개의 부등호 관계를 모두 만족시키는 (k+1)개 자리의 정수 중에서 최대 값과 최소 값을 구하는 문제

이 문제를 푸는 가장 기본적인 방법은 모든 정수를 다 넣어보고 부등호를 만족시킬 때 기존의 값과 비교하여 최대값 및 최솟값을 갱신하는 것이다.

예를 들어, A = ? < ? > ? < ? 이면 3 < 6 > 5 < 7 이 들어가면 만족한다. 문제의 조건에 따라 생각해보면, 1) 0~9까지의 수 중에서 4개를 고른다. 2) 4개의 수를 모든 순서에 따라 넣어보면서 부등호를 만족하는지 확인한다. 이렇게 두 가지 과정으로 나눌 수 있다.

1) 10개의 수(0 ~ 9) 중에서 k+1 개를 고른다. -> 2^(k+1)
2) (k+1)!개의 순서를 모두 만들고, -> (k+1)!
3) 부등호가 맞는지 검사한다. -> k+1

이때 총 시간복잡도는 2^(k+1) (k+1)! (k+1) 이다.
k ≤ 9 이면, k + 1 ≤ 10 이므로 시간복잡도는 2^10 10! 10 = 1024 3,628,800 10 ≒ 36,288,000,000 인데, 이것은 너무 큰 복잡도이다.

성능 개선

여기서 시간을 줄이려면 불필요한 탐색을 줄여야한다.

? < ? > ? < ? 에서 3 5 6 7을 골랐다면
3 < 6 > 5 < 7 이 경우에 부등호를 만족하는데,
6 < 8 > 7 < 9 여기서 9 8 7 6으로도 무조건 부등호를 만족시킬 수 있다.

그렇다면 4개의 수를 고르는 과정에서 가장 큰 수 4개를 고르면 무조건 부등호를 만족하는 조합이 있으며, 그 중에서 가장 큰 순열이 전체 중에서 가장 큰 수가 된다. 가장 작은 수도 마찬가지로 생각해볼 수 있다.

부등호에 들어가는 수는 어떤 조합이라도 무조건 부등호를 만족하는 순열이 만들어진다. 따라서 이 문제에서는 수의 대소관계는 중요하지만, 실제로 그 수가 무엇인지는 중요하지 않다. 왜냐하면 이 문제는 가장 큰 수와 작은 수를 찾는 것이기 때문이다.

• k ≤ 9
• k + 1 ≤ 10
• 선택된 숫자는 모두 달라야하기 때문에, 가능한 수의 개수는 10!개 이다
• 모두 해보고, 가장 큰 수와 작은 수를 구해본다.

k+1개의 숫자를 가장 큰수의 구성으로 미리 선택하면 선택하는 시간 2^(k+1)을 없앨 수 있다.

1) 10개의 수(0 ~ 9) 중에서 k+1 개를 고른다. -> 2^(k+1)
2) (k+1)!개의 순서를 모두 만들고, -> (k+1)!
3) 부등호가 맞는지 검사한다. -> k+1

또 다른 예시를 들어보면,

• 입력으로 주어진 부등호가 < > 이고
• 가장 큰 수를 구하는 경우를 생각해보면
• 이 부등호에는 숫자가 총 3개 필요하기 때문에, 가장 큰 숫자 3개인 9, 8, 7로 구성되는 것이 정답임을 알 수 있다.
• 반대로 가장 작은수를 구하는 경우에는 0, 1, 2로 구성되는 것이 정답이 된다.

2. 문제 풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool check(vector<int> &perm, vector<char> &a) { // 서로 다른 수가 사이의 부등호를 만족하는지 검사
    for (int i=0; i<a.size(); i++) {
        if (a[i] == '<' && perm[i] > perm[i+1]) {
            return false;
        }
        if (a[i] == '>' && perm[i] < perm[i+1]) {
            return false;
        }
    }
    return true;
}
int main() {
    int k;
    cin >> k;
    vector<char> a(k);
    for (int i=0; i<k; i++) {
        cin >> a[i];
    }
    vector<int> small(k+1);	// the biggest number
    vector<int> big(k+1);	// the smallest number
    for (int i=0; i<=k; i++) {
        small[i] = i;	// 0 ~ k -> 0 1 2 3 ...
        big[i] = 9-i;	// (9 - k) -> 9 8 7 6 ...
    }
    do { // 부등호를 만족하는 가장 작은 수를 찾음 0123 0132 ...
        if (check(small, a)) {
            break;
        }
    } while(next_permutation(small.begin(), small.end()));
    do { // 부등호를 만족하는 가장 큰 수를 찾음 9876 9867 ...
        if (check(big, a)) {
            break;
        }
    } while(prev_permutation(big.begin(), big.end()));
    for (int i=0; i<big.size(); i++) {
        cout << big[i];
    }
    cout << '\n';
    for (int i=0; i<small.size(); i++) {
        cout << small[i];
    }
    cout << '\n';
    return 0;
}