백준 2529. 부등호

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

2529번: 부등호

 

이 문제는 생각해보면 결국 모든 순열 조합을 만들어서 부등호를 비교해 조건에 만족하는 순열들 중 가장 큰 순열과 가장 작은 순열을 찾는 것이다.

 

DFS와 백트랙킹을 이용해서 이전과 똑같이 순열을 만들고 부등호 관계가 옳은지를 확인한후 옳다면 ans 벡터에 넣어놓고 마지막에 정렬해서 가장 첫원소와 마지막 원소를 출력한다.

 

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

#define MAX 10
using namespace std;

int k;
int nums[MAX];
bool mark[MAX];
char sign[MAX];

// string형태로 저장된 순열들의 집합
vector<string> ans;
// 순열들의 숫자들이 저장됨
vector<char> v;

// 벡터에 들어있는 k개의 숫자들과 부등호의 관계를 비교
// 하나라도 관계가 틀리면 false 리턴
// 모두 옳다면 true 리턴
bool Compare() {
    bool res = true;
    for(int i = 0; i < k; i++) {
        if(sign[i] == '<') {
            // char형을 int형으로 바꿔서 계산
            if(!(v[i]-'0' < v[i+1]-'0')) return false;
        }
        else if(sign[i] == '>') {
            if(!(v[i]-'0' > v[i+1]-'0')) return false;
        }
    }

    return true;
}

void DFS(int depth) {
    if(depth == k+1) {
        // 모든 부등호 관계가 옳다면
        if(Compare()) {
            string temp = "";
            for(int i = 0; i < v.size(); i++) {
                temp += v[i];
            }
            // 만들어진 string을 ans 벡터에 푸쉬
            ans.push_back(temp);
        }
        // 이전 depth로 리턴
        return;
    }


    for(int i = 0; i < 10; i++) {
        if(mark[i]) continue;

        mark[i] = true;
        // +'0'을 함으로서 int형을 char형으로 변환해서 벡터에 저장
        v.push_back(nums[i]+'0');

        DFS(depth+1);

        v.pop_back();
        mark[i] = false;
    }
}

int main() {
    cin >> k;
    // 부등호 sign[]에 저장
    for(int i = 0; i < k; i++)
        cin >> sign[i];

    // 0~9까지의 숫자
    for(int i = 0; i < 10; i++)
        nums[i] = i;

    DFS(0);
    // ans 벡터를 정렬
    sort(ans.begin(), ans.end());

    cout << ans[ans.size()-1] << '\n';
    cout << ans[0] << '\n';

}

 

algorithm 라이브러리의 sort 함수가 char나 string 형식의 데이터도 소팅해주는지 처음 알았다.

 

 

 

 

temp

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int k;
char sign[10];
int nums[10];
int mark[10];
vector<int> v;

long long highest = -1;
long long lowest = 0;
bool trigger = false;
int once = 0;

bool Compare(int depth) {
    if(depth <= 1) return true;

    if(sign[depth-2] == '>') {
        if(v[depth-2] > v[depth-1])
            return true;
        else
            return false;
    }
    else {
        if(v[depth-2] < v[depth-1])
            return true;
        else
            return false;
    }

}

void HighestLowest() {
    long long num = 0;
    long long ten = 1;
    for(int i = v.size()-1; i >= 0; i--) {
        if(v[i] == 0) {
            ten *= 10;
            continue;
        }
        num += v[i] * ten;
        ten *= 10;
    }
    if(once == 0) {
        cout << "num: " << num << endl;
        once++;
    }
    if(num > highest)
        highest = num;

    if(!trigger) {
        trigger = true;
        lowest = num;
    }
    if(num < lowest)
        lowest = num;

    /*cout << "num: " << num << endl;
    cout << "lowest: " << lowest << endl;*/
}

void Print() {
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ' ';
    } cout << endl;
}

void DFS(int depth) {
    if(depth == k+2) {
        Print();
        HighestLowest();
        return;
    }

    for(int i = 0; i < 10; i++) {
        if(mark[i]) continue;

        mark[i] = true;
        // 벡터에 삽입
        v.push_back(nums[i]);

        // 부등호와 비교해서 false라면 이전 depth로
        if(!Compare(depth)) {
            v.pop_back();
            mark[i] = false;
            return;
        }


        DFS(depth+1);

        mark[i] = false;
        v.pop_back();
    }
}

int main() {
    cin >> k;

    for(int i = 0; i < 10; i++) {
       nums[i] = i;
    }

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


    DFS(1);
    cout << lowest << endl;
    cout << highest << endl;
}