[백준] 2529 부등호

Peace·2021년 1월 1일
0

[백준] 2529 부등호

문제 링크: https://www.acmicpc.net/problem/2529

문제 접근

시간 초과된 접근(?)

처음에는 brute force문제여서 진짜 완전 다 계산을 했다.
겹치는 숫자들도 포함해서 계산을 했다. 비록 그 숫자가 겹치는 숫자가 있으면, 부등호에 맞는지에 대해서는 계산을 안했는데, 그래도 그것들이 겹치는 숫자인지 여부를 계산을 했기 때문에, 시간이 많이 들어간 거 같다. 이 때문에 결과는 올바르게 나오지만, 시간 초과가 나왔다.

문제 해결 방법

도저히 어떻게 풀지 모르겠어, 인터넷에서 푸는 방법에 대해 찾아 봤다. 이 문제는 순열과 dfs를 사용해서 풀면 가능하다고 나와있었다. 서로 다른 숫자들을 순서대로 나열한다는 것이 순열에 부합했고, 서로 다른 숫자들을 backtracking하여 탐색하는 것이 dfs에 부합했다.

그래서 나는 vector를 사용하여 dfs를 구현하였다. 현재 vector안에 들어가 있는 숫자들을 확인하기 위해, 숫자 10개의 boolean 배열을 구성하였다. 그래서 만약 숫자가 부등호 수 보다 1개가 많다면, 부등호에 부합하 지에 대해 평가를 하였다. 부합한다면, result vector에 넣었다. 그리고 dfs가 끝난 후에, 0에서 부터 dfs를 구성하였기 때문에, 맨 앞에 있는 값이 가장 작은 값이고, 가장 마지막에 있는 값이 가장 큰 수이기 때문에, 처음과 끝을 출력하였다.

코드 구현

시간 초과된 코드.

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

using namespace std;

vector<int> result;
bool check_true_num(string number, string symbol, int len){
    bool check = true;
    for(int j = 0 ; j < len ; j++){
        if(symbol[j] == '>'){
            if(number[j] > number[j+1]) check = true;
            else {
                check = false;
                break;
           }
        }
        else if(symbol[j] == '<'){
            if(number[j] < number[j+1]) check = true;
            else {
                check = false;
                break;
            }
        }
    }
    return check;
}

bool check_same_num(string number){
    for(int i = 0; i < number.length(); i++){
        for(int j = i+1; j < number.length(); j++){
            if(number[i] == number[j]) return false;
        }
    }
    return true;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int num;
    scanf("%d",&num);
    string symbol;
    for(int i = 0; i < num; i++){
        cin >> symbol[i];
    }
    int max_num = 1;
    for(int i = 0; i <= num; i++){
        max_num = max_num*10;
    }
    for(int i = 1; i <= max_num; i++){
        bool check = true;
        string temp = to_string(i);
        if (temp.length() > num) temp = temp;
        else if(temp.length() == num) temp = "0" + temp;
        else continue;
        check = check_true_num(temp, symbol, num);
        if(!check) continue;
        check = check_same_num(temp);
        if(check) result.push_back(i);
    }
    sort(result.begin(),result.end());
    int ten = 1;
    int ten_check = result[0];
    while(1){
        ten_check = ten_check/10;
        if(ten_check == 0) break;
        ten++;
    }
    if(ten == num) printf("%d\n0%d\n",result.back(),result[0]);
    else printf("%d\n%d\n",result.back(),result[0]);
}

DFS로 구현한 코드

#include <iostream>
#include <vector>

using namespace std;

vector<string> result;
vector<int> check_num;
bool check[10];
string symbol;
int num;
bool check_true_number(){
    for(int i = 0 ; i < num ; i++){
        if(symbol[i] == '<'){
            if(!(check_num[i] < check_num[i+1])) return false;
        }
        else{
            if(!(check_num[i] > check_num[i+1])) return false;
        }
    }
    return true;
}
string make_num_str(){
    string result_str = "";
    for(int i = 0 ; i < num + 1 ; i++){
        result_str += to_string(check_num.at(i));
    }
    return result_str;
}
void dfs(int count){
    if(count == num+1){
        if(check_true_number()){
            string result_str = make_num_str();
            result.push_back(result_str);
        } 
    }
    else{
        for(int i = 0; i <= 9 ; i++){
            if(!check[i]){
                check_num.push_back(i);
                check[i] = true;
                dfs(count+1);
                check[check_num.back()] = false;
                check_num.pop_back();
            }
        }
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> num;
    for(int i = 0 ; i < num ; i++){
        cin >> symbol[i];
    }
    dfs(0);
    cout << result.back() << endl;
    cout << result.front() << endl;

}

평가

평소에도 구현할 때, 가장 효율적이고 빠른 코드로 구현하기 위해 노력해야겠다. 문제를 풀어갈 때 사용하는 기법(?)은 문제를 많이 풀어봐야지 알 것 같다는 생각이 들었다. 만약 풀고, 안된다면 다른 사람들이 문제 접근한 것을 보고 배우는 것도 좋은 방법인 것 같다.

profile
https://peace-log.tistory.com 로 이사 중

0개의 댓글