[프로그래머스/C++] 수식복원하기 [Lv. 3]

실패한 접근 방법..

구현 문제이기에 내용은 간단하다. 주어진 수식을 통해 몇진수인지 확인하고, 만약 2개 이상의 진수로 판단이 되어 다수의 정답이 나오는 경우는 ?로 표현한다. 만약, 특정 진수로 판단이되면 그 진수로 나머지 답을 구한다.

 

나는 처음에  진수에 대한 계산을 직접 구현하려고 했다. 한자리수끼리 계산을 해서 n진수 값보다 이상이면 한자리수를 더하거나 빼서 계산을 진행했다. 근데 이 방식의 문제는 10진수와 n진수간의 혼동이 온다는 것이다. 

 

분명 이론상으로는 잘 고려해서 코드를 짠거 같지만.. 제출을 해보니 73점.. 어디선가 로직 혹은 예외처리가 잘못된거 같다. 이틀에 걸쳐서 찾아내려고 노력을 했지만 역시 불가능했다. 결국 다른 방법을 찾아야만 했다.. (내 시간들 ㅠㅠㅠ) 

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <math.h>
//X가 아닌 것들을 추리기
//전부다 노출된 값들에 대해서 op와 숫자를 추출하기
//최대 숫자값을 구하기 -> 그값 +1이 n진수시작값임
//맨 뒷자리수만 계산해서 n진수인지 확인
//만약 다 되면 ?로 지정
//특정 n진수만 되면 그걸로 X값 도출
using namespace std;

string solveUnknown(string num1, string op, string num2, int base, int minBase) {
    int n1_size = num1.size()-1;        
    int n2_size = num2.size()-1;
    if(base == -1){
        while(n1_size>=0 || n2_size>=0){
            int n1 = (n1_size>=0)?num1[n1_size--]-'0':0;
            int n2 = (n2_size>=0)?num2[n2_size--]-'0':0;

            if(op=="+") {
                if(n1+n2>=minBase) return "?";
            } else if(op=="-"){
                if(n1-n2>=minBase || n1-n2<0) return "?";
            }
        }
        base = minBase;
    }
    
    n1_size = num1.size()-1;        
    n2_size = num2.size()-1;
    int total=0, pos = 0, carry =0;
    
    while(n1_size>=0 || n2_size>=0 || carry!=0){
        int n1= (n1_size>=0) ? num1[n1_size--]-'0':0;
        int n2= (n2_size>=0) ? num2[n2_size--]-'0':0;
        int sum =0;

        if(op=="+"){
            sum = n1 +n2+carry;
            carry = (sum>=base)?1:0;
            sum = (sum>=base)?sum-base:sum;
        } else if(op=="-"){
            sum = n1 - n2 + carry;
            carry = (sum<0)?-1:0;
            sum = (sum<0)?sum+base:sum;
        }

        total += sum * pow(10,pos++);
    }

    return to_string(total);
}

bool isValidExpression(string num1, string op, string num2, string num3, int base) {
    string result = solveUnknown(num1,op,num2,base,base);
    if(num3 == result) return true;
    else return false;
}

vector<string> solution(vector<string> expressions) {
    vector<string> answer;
    vector<string> unknown_expr, known_expr;
    
    for(auto expr: expressions){
        stringstream ss(expr);
        string num1, op, num2, equel, num3;
        ss >> num1 >> op >> num2 >> equel >> num3;
        
        if(num3 =="X") unknown_expr.push_back(expr);
        else known_expr.push_back(expr);
    }
    
    int minBase = 1;
    for(auto expr: expressions){
        stringstream ss(expr);
        string num1, op, num2, equel, num3;
        ss >> num1 >> op >> num2 >> equel >> num3;
        
        for (char c : num1) minBase = max(minBase, c - '0');
        for (char c : num2) minBase = max(minBase, c - '0');
        if (num3 != "X") for (char c : num3) minBase = max(minBase, c - '0');
    }

    minBase++;

    vector <int> possible_base;
    for(int base =minBase; base<10; base++){
        bool valid = true;
        for(auto expr: known_expr){
            stringstream ss(expr);
            string num1, op, num2, equel, num3;
            ss >> num1 >> op >> num2 >> equel >> num3;
            valid = isValidExpression(num1, op, num2, num3, base);
        }
        if(valid) possible_base.push_back(base);
    }
    
    for(auto expr: unknown_expr){
        stringstream ss(expr);
        string num1, op, num2, equel, num3;
        ss >> num1 >> op >> num2 >> equel >> num3;
        
        string ans;
        ans+= num1 +" " + op +" " + num2 +" " + equel +" ";
        
        if(possible_base.size()>1) ans += solveUnknown(num1, op, num2, -1, minBase);
        else ans += solveUnknown(num1, op, num2, possible_base[0], minBase);
        cout << possible_base.size() <<"::" << possible_base[0] <<"::"<<minBase <<endl;
        answer.push_back(ans);
    }
    return answer;
}

 

새로운 접근

10진수와 n진수간의 계산법은 다르기에 10진수로 모두다 변환을 해서 우리가 아는 10진수 계산법으로 진행하면 어떨까 하는 생각이 들었다. (사실은 gpt의 도움으로 접근법을 알아냈다..ㅎㅎ)

 

처음에는 이해가 안되었지만 우리가 아는 2진수 계산법을 생각하면 이 방식이 이해가 될것이다.

10진수 5를 2진수로 변환하기 위해 우리는 아래 방식을 따른다

1. 5를 2로 나눈다.
2. 그 나머지 값이 2진수의 첫번째 값이 된다. (나머지: 1)
3. 그리고 2로 나눈 몫이 다음 나눌 값이 된다. (즉, 5 -> 2(몫)로 진행됨)
4. 5가 0이 될때까지 계속 2로 나누면서 반복한다. (두번째 2진수 값은 0이 됨)
5. 최종적으로는 101된다.

이거를 코드로 만들면 아래와 같다.

string decimal_to_baseN(int num, int base){
    if(num==0) return "0";
    string result;
    while(num>0){
        result = to_string(num%base)+result;
        num /=base;
    }
    return result;
}

 

이러한 방식이 만약 n진수라면? 위 방식의 2가 n으로 바뀔뿐 방식은 동일하다. 

그렇다면 10진수를 n진수로 바꾸는 것은 어떻게 하면 될까?

이것도 2진수를 10진수로 바꾸는 방식을 생각하면 쉽다.

1. k번째 자리수에 대해서 2의 k승만큼 그자리수를 곱하면 됨
2. 2^2*1 + 2^1*0 + 2^0*1 = 5

이거를 코드로 만들면 아래와 같다. 

int baseN_to_decimal(string num1, int base){
    int total =0,pos=num1.size()-1;
    for(char c: num1){
        total += pow(base,pos--)*(c-'0');
    }
    return total;
}

 

자.. 그러면 헷갈리면 안되는 점을 말하고 바로 전체 코드를 보여주겠다. (내가 이부분이 헷갈렸기에 적어둔다 ㅎㅎ)

주어진 expressions은 n진수로 표현된 값들이다. 그렇기에 expressions 숫자들을 모두 10진수로 바꾸고 계산한다.

 

정답은 다음 흐름과 같다.

1. 전부다 공개된 수식들과 X로 표현된 수식들을 따로 저장한다.
2. 모두 공개된 수식들에 대한 숫자로 가능한 n진수를 찾는다.
3. 가능한 n진수에 대하여 가능한 X값을 모두 구한다.
4. 만약 가능한 X값이 2개 이상이면 ?로 표현하고, 딱 1개만 존재하면 X값을 그값으로 표현한다.

[중요] 2번을 진행할때 expressions 숫자를 10진수로 바꾸고 계산한뒤, 다시 n진수로 바꾼 결과값을 비교하여 수식의 값과 동일한지 확인한다..! 

 

//우리가 아는 2진수는 cba에 대해서 2^0*a + 2^1*b + 2^2*c..으로 값을 구한다.
//이거는 실제 5진수에서도 동일한 방식으로 10진수 변환이 가능하다

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <math.h>
#include <set>

using namespace std;

int baseN_to_decimal(string num1, int base){
    int total =0,pos=num1.size()-1;
    for(char c: num1){
        total += pow(base,pos--)*(c-'0');
    }
    return total;
}

//45를 2진수로 바꿀때 나머지가 값이 되고 몫이 45다음 수가 됨.
string decimal_to_baseN(int num, int base){
    if(num==0) return "0";
    string result;
    while(num>0){
        result = to_string(num%base)+result;
        num /=base;
    }
    return result;
}

string solveUnknown(string num1, string num2, string op, int base){
    int x = baseN_to_decimal(num1,base);
    int y = baseN_to_decimal(num2,base);

    int result = (op=="+") ? x+y:x-y;
    return decimal_to_baseN(result, base);
}

// 주어진 수식이 해당 진법에서 성립하는지 확인
bool isValid(string a, string op, string b, string c, int base) {
    int x = baseN_to_decimal(a, base);
    int y = baseN_to_decimal(b, base);
    int z = baseN_to_decimal(c, base);

    if (op == "+") return x + y == z;
    if (op == "-") return x - y == z;
    return false;
}

vector<string> solution(vector<string> expressions) {
    vector<string> answer;
    vector<string> unknown_expr, known_expr;
    
    for(auto expr: expressions){
        stringstream ss(expr);
        string num1, op, num2, equel, num3;
        ss >> num1 >> op >> num2 >> equel >> num3;
        
        if(num3 =="X") unknown_expr.push_back(expr);
        else known_expr.push_back(expr);
    }
    
    int minBase = 1;
    for(auto expr: expressions){
        stringstream ss(expr);
        string num1, op, num2, equel, num3;
        ss >> num1 >> op >> num2 >> equel >> num3;
        
        for (char c : num1) minBase = max(minBase, c - '0');
        for (char c : num2) minBase = max(minBase, c - '0');
        if (num3 != "X") for (char c : num3) minBase = max(minBase, c - '0');
    }

    minBase++;

    set<int> possible_base;
    for(int base =minBase; base<10; base++){
        bool valid = true;
        for(auto expr: known_expr){
            stringstream ss(expr);
            string num1, op, num2, equel, num3;
            ss >> num1 >> op >> num2 >> equel >> num3;
            if (!isValid(num1, op, num2, num3, base)){
                valid = false;
                break;
            }
        }
        if(valid) possible_base.insert(base);
    }

    for(auto expr: unknown_expr){
        set<string> results;
        stringstream ss(expr);
        string num1, op, num2, equel, num3;
        ss >> num1 >> op >> num2 >> equel >> num3;
        
        string ans;
        ans+= num1 +" " + op +" " + num2 +" " + equel +" ";
        
        for(auto base: possible_base){
            results.insert(solveUnknown(num1, num2, op, base));
        }
        
        if(results.size()==1) ans += *results.begin();
        else ans += "?";

        answer.push_back(ans);
    }
    
    return answer;
}