[2529] 부등호(C++)

문제

바로가기

두 종류의 부등호 기호 <와 >가 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인 경우도 정수에 포함되어야 한다.

모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다.

 

 

알고리즘

• 브루트포스
• 백트래킹

 

 

해결 방법

k의 최댓값은 9이므로 부등호 사이사이에 넣어야 할 숫자의 최대 개수는 10개이다.

그리고 여기에 사용될 숫자도 0 ~9 까지 10개이다.

부등호에 상관없이 (K + 1)자리에 0 ~ 9까지의 숫자를 순서있게 나열하는 경우를 생각해보면 10 X 9 X 8 X .... X 1 = 10!이다.

10! < 1억이므로 모든 경우를 구해도 1초안에 해결할 수 있기 때문에 이 문제는 브루트포스로 풀 수 있는 것

 

브루트포스가 가능하다는 것을 알았으니 이제 0부터 9까지의 숫자 중에 중복되지 않게 (K + 1)개의 수를 선택하고 순열을 만들면 된다.

 

이때 순열을 만드는 방법은 2가지가 있다.

1️⃣  C++ <algorithm> 헤더에 내장되어있는 next_permutation 함수 사용
2️⃣  백트래킹으로 순열 직접 구현

1번을 사용하면 굉장히 간단하게 순열을 구할 수 있긴하지만 혹시 모를 상황을 대비해 나는 보통 직접 구현하는 방식을 선택한다.

2번은 한번만 제대로 구현해두면 코드의 약간 변형을 통해 조합, 중복조합, 중복순열까지 구현할 수 있으니 1, 2번 둘 다 알아두면 좋을 것 같다.

 

문제 접근 방식도 크게 숫자로 접근하느냐, 문자로 접근하느냐로 나눠볼 수 있을 것 같은데 아래에 두가지 방법으로 모두 풀이해놨으니 선호하는 스타일대로 풀면 될 것 같다.

문자열을 사용한 방식이 메모리는 좀 더 잡아먹었지만 시간 측면에서는 훨씬 빨랐다.

 

 

내 코드(C++)

// [2529] 부등호
// 문자열 접근
// 3576KB, 8ms
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int k;
char inequal[11];
bool visited[11];
vector <string> list;

bool check(char a, char b, char oper)
{
    if(oper == '<' && (a > b)) return false;
    else if(oper == '>' && (a < b)) return false;
    return true;
}

void dfs(int cnt, string num)
{
    if(cnt == k + 1) {
        list.push_back(num); // 정답 가능 리스트에 추가
        return;
    }

    for(int i = 0 ; i <= 9 ; i++) {
        if(visited[i] == false && check(num[cnt - 1], i + '0', inequal[cnt - 1])) {
            visited[i] = true;
            dfs(cnt + 1, num + to_string(i));
            visited[i] = false;
        }
    }
}

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

    dfs(0, "");
    sort(list.begin(), list.end());
    cout << list[list.size() - 1] << '\n';
    cout << list[0] << '\n';
    return 0;
}

// [2529] 부등호
// 2208KB, 144ms
#include <iostream>
#include <cmath>
using namespace std;

bool visited[10];
char sign[10];
int k, tmpNum[10];
long long maxNum = 0, minNum = 9876543210;

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

bool check()
{
    for(int i = 0; i < k; i++) {
        if(tmpNum[i] < tmpNum[i+1] && sign[i] == '>') {
            return false;
        }
        else if(tmpNum[i] > tmpNum[i+1] && sign[i] == '<') return false;
    }
    return true;
}

void update()
{
    long long num = 0, idx = 1;
    for(int i = k; i >= 0; i--) {
        num += tmpNum[i] * idx;
        idx *= 10;
    }
    if(num > maxNum) maxNum = num;
    if(num < minNum) minNum = num;
}

void dfs(int idx, int depth)
{
    if(depth == k + 1) {
        if(check() == true) {
            update();
        }
        return;
    }
    for(int i = 0; i < 10; i++) {
        if(visited[i] == false && i != idx) {
            visited[i] = true;
            tmpNum[depth] = i;
            dfs(i, depth + 1);
            visited[i] = false;
        }
    }
}

void output()
{
    if(maxNum < pow(10, k)) cout << "0";
    cout << maxNum << '\n';

    if(minNum < pow(10, k)) cout << "0";
    cout << minNum << '\n';
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    dfs(-1, 0);
    output();

    return 0;
}