[프로그래머스] 수식 복원

문제 설명

당신은 덧셈 혹은 뺄셈 수식이 여러 개 적힌 고대 문명의 유물을 찾았습니다. 이 수식들을 관찰하던 당신은 이 문명이 사용하던 진법 체계가 10진법이 아니라는 것을 알아냈습니다. (2 ~ 9진법 중 하나입니다.)

수식들 중 몇 개의 수식은 결괏값이 지워져 있으며, 당신은 이 문명이 사용하던 진법에 맞도록 지워진 결괏값을 채워 넣으려 합니다.

다음은 그 예시입니다.

<수식>

14 + 3 = 17
13 - 6 = X
51 - 5 = 44

• X로 표시된 부분이 지워진 결괏값입니다.

51 - 5 = 44에서 이 문명이 사용하던 진법이 8진법임을 알 수 있습니다. 따라서 13 - 6 = X의 지워진 결괏값을 채워 넣으면 13 - 6 = 5가 됩니다.

다음은 또 다른 예시입니다.

<수식>

1 + 1 = 2
1 + 3 = 4
1 + 5 = X
1 + 2 = X

주어진 수식들에서 이 문명에서 사용한 진법이 6 ~ 9진법 중 하나임을 알 수 있습니다.
1 + 5 = X의 결괏값은 6진법일 때 10, 7 ~ 9진법일 때 6이 됩니다. 이와 같이 결괏값이 불확실한 수식은 ?를 사용해 1 + 5 = ?와 같이 결괏값을 채워 넣습니다.
1 + 2 = X의 결괏값은 6 ~ 9진법에서 모두 3으로 같습니다. 따라서 1 + 2 = X의 지워진 결괏값을 채워 넣으면 1 + 2 = 3이 됩니다.

덧셈 혹은 뺄셈 수식들이 담긴 1차원 문자열 배열 expressions가 매개변수로 주어집니다. 이때 결괏값이 지워진 수식들의 결괏값을 채워 넣어 순서대로 문자열 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

---

제한사항

• 2 ≤ expressions의 길이 ≤ 100
  • expressions의 원소는 "A + B = C" 혹은 "A - B = C" 형태의 문자열입니다. A, B, C와 연산 기호들은 공백 하나로 구분되어 있습니다.
  • A, B는 음이 아닌 두 자릿수 이하의 정수입니다.
  • C는 알파벳 X 혹은 음이 아닌 세 자릿수 이하의 정수입니다. C가 알파벳 X인 수식은 결괏값이 지워진 수식을 의미하며, 이러한 수식은 한 번 이상 등장합니다.
  • 결괏값이 음수가 되거나 서로 모순되는 수식은 주어지지 않습니다.

풀이

가능한 진법의 범위를 좁히거나, 특정시키는 방법을 생각해 내는 문제.

 

- 진법의 범위 좁히기 : {수식에 사용된 최대 기수 + 1} 이 최소 진법임.

예를 들면 [ 55 + 55 = X ] 이라는 수식이 있을 때, 사용된 최대 기수는 5 이다.

그렇다면 이 문제에서 가능한 진법은 6(5 + 1)진법 ~ 9진법 이다.

 

- 진법 특정 시키기 : 수식의 계산 결과가 10진법으로 계산한 결과와 다를 경우, 진법(N)을 특정 가능하다.

왜냐하면 10진법과 다르다는 것은 N 진법으로 계산한 결과 올림 혹은 내림이 발생했다는 뜻이고, 이럴 경우 올림된 나머지가 N에 의해 정해지기 때문에 단 한 가지 진법으로 특정 가능하다.

여기서 N을 계산해 내는 방법은 단순히 범위 내의 모든 진법(N)에 대해서 결과를 계산하고 맞는지 비교해 보면 된다.

 

- 좁혀진 진법 범위로 결과가 X인 수식의 결과 계산하기.

최소 진법과 최대 진법을 한 번씩 계산해 보고, 두 계산 결과가 같으면 X를 특정할 수 있다.

두 계산 결과가 다를 경우 결과 값을 ? 로 둔다.

코드

#include <string>
#include <vector>
#include <cmath>
#include <iostream>
#include <sstream>

using namespace std;
int MinN = 2;
int MaxN = 9;
vector<string> SplitExp(string exp)
{
    stringstream ss(exp);
    vector<string> splitedExp(5);
    int i = 0;
    while(ss>>splitedExp[i++]);
    return splitedExp;
}
int ToDecimal(int number, int N)
{
    int result = 0;
    int digit = 1;
    int numerator = number;
    while(numerator != 0)
    {
        result += numerator%10 * digit;
        digit *= N;
        numerator /= 10;
    }
    return result;
    
}
int ToNSystem(int number,int N)
{
    int numerator = number;
    int result = 0;
    int digit = 1;
    while(numerator != 0)
    {
        result += numerator%N *digit; 
        digit *= 10;
        numerator /= N;
    }
    return result;
}
string SolveExp(string A, string B, bool add, int N)
{

    int ADecimal = ToDecimal(stoi(A),N);
    int BDecimal = ToDecimal(stoi(B),N);
   // cout <<"ADecimal : "<<ADecimal<<endl;
    //cout <<"BDecimal : "<<BDecimal<<endl;
    int resultDecimal = add? ADecimal+BDecimal : ADecimal-BDecimal;
    string result = "";
    result = to_string(ToNSystem(resultDecimal,N));
    return result;
    
}
int SpecifyN(vector<vector<string>>& nonXExps)
{
    for(auto exp : nonXExps)
    {
        int reusultDecimal = exp[1] == "+" ? 
                stoi(exp[0]) +  stoi(exp[2]) 
                :  stoi(exp[0]) -  stoi(exp[2]);
        if(reusultDecimal == stoi(exp[4]))
            continue;
        for(int i = MinN ; i <= MaxN ; i++)
        {
            string resultN = SolveExp(exp[0], exp[2], exp[1] == "+", i);
            if(resultN == exp[4])
                return i;
        }
        
    }
    return -1;
}
vector<string> solution(vector<string> expressions) {
    vector<string> answer;
    vector<vector<string>> nonXExps;
    vector<vector<string>> xExps;
    for(auto exp : expressions)
    {
        vector<string> splitedExp = SplitExp(exp);
        for(auto token : splitedExp)
        {
            for(auto c : token)
                if(c >= '0' && c <= '9')
                    MinN = max(c-'0'+1, MinN);
        }
        if(splitedExp[4] == "X")
            xExps.push_back(splitedExp);   
        else
            nonXExps.push_back(splitedExp);   
    }
    int SpecifyResult = SpecifyN(nonXExps);
    if(SpecifyResult > 0)
    {
        MinN = SpecifyResult;
        MaxN = SpecifyResult;
    }
    cout<<"MinN : "<<MinN<< ", MaxN : "<<MaxN<<endl;
    for(auto exp : xExps)
    {
        string minX =SolveExp(exp[0], exp[2], exp[1] == "+", MinN);
        string maxX =SolveExp(exp[0], exp[2], exp[1] == "+", MaxN);
        exp[4] = minX == maxX ? minX : "?";
        string ans = "";
        for(auto t : exp)
            ans += t +" ";
        ans.erase(ans.end()-1);
        answer.push_back(ans);
    }
    return answer;
}