[1일 1알고] [PCCP 기출문제] 4번 / 수식 복원하기

그동안 문제는 계속 풀었는데 포스팅을 못했었네요

오늘은 약간 복잡한 문제었던김에 적어보려고 합니다.

 

2~9진법 중 하나를 사용하는 체계일 때 expresion 의 X를 채워넣어야합니다.

 

예를 들어 expressions가 ["14 + 3 = 17", "13 - 6 = X", "51 - 5 = 44"] 라면 51-5=44를 통해 8진법임을 알 수 있습니다.

다만 ["1 + 1 = 2", "1 + 3 = 4", "1 + 5 = X", "1 + 2 = X"]라면 1+2가 3인 것은 1+3이 4임을 통해 알 수 있지만, 1+5에 대해서는 6, 7, 8, 9 진법인지 알 수 없습니다. 따라서 1+5=?가됩니다.

---

따라서 해야할 것은 2~9진법까지 그냥 하나하나 해가면서 정합한지 확인하는 것입니다.

 

다만 expression에서 등장한 최대숫자 이하의 진법은 나올 수 없기 때문에(예를 들어 1 + 8 = '?'라면 9진법외에는 나올 수 없음)

이를 통해 범위를 좁힌 뒤 탐색해볼 수 있습니다.

---

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <math.h>
#include <climits>
#include <unordered_map>
using namespace std;

struct expression
{
    string a, b, c;
    char oper;
};

vector<expression> exps;
int max_num = 1;

void parsing(string& exp_str)
{
    int idx = 0;
    string temp = "";
    expression exp;

    for (int i = 0; i < exp_str.size(); ++i)
    {
        if (exp_str[i] >= '0' && exp_str[i] <= '9')
        {
            temp += exp_str[i];
            max_num = max(max_num, exp_str[i] - '0');
        }
        else if (exp_str[i] == '+' || exp_str[i] == '-')
        {
            exp.a = temp;
            temp = "";
            exp.oper = exp_str[i];
        }
        else if (exp_str[i] == '=')
        {
            exp.b = temp;
            temp = "";
        }
    }

    if (temp == "")
    {
        exp.c = "X";
    }
    else
    {
        exp.c = temp;
    }

    exps.push_back(exp);
}

vector<string> solution(vector<string> expressions) {
    vector<string> answer;

    exps.clear();
    max_num = 1;

    for (int i = 0; i < expressions.size(); ++i)
    {
        parsing(expressions[i]);
    }

    vector<int> results;

    for (int i = max_num + 1; i <= 9; ++i)
    {
        bool flag = true;

        for (expression& exp : exps)
        {
            if (exp.c == "X")
                continue;

            int a = 0, b = 0, c = 0;

            for (int idx = 0; idx < exp.a.size(); ++idx)
            {
                a = a * i + (exp.a[idx] - '0');
            }
            for (int idx = 0; idx < exp.b.size(); ++idx)
            {
                b = b * i + (exp.b[idx] - '0');
            }
            for (int idx = 0; idx < exp.c.size(); ++idx)
            {
                c = c * i + (exp.c[idx] - '0');
            }

            if (exp.oper == '+' && a + b != c)
            {
                flag = false;
                break;
            }
            else if (exp.oper == '-' && a - b != c)
            {
                flag = false;
                break;
            }
        }

        if (flag)
            results.push_back(i);
    }

    for (expression& exp : exps)
    {
        if (exp.c != "X") continue;

        string ans = "";
        ans += exp.a;
        ans += ' ';
        ans += exp.oper;
        ans += ' ';
        ans += exp.b;
        ans += " = ";

        string result_str = "";
        bool same = true;

        for (int result : results)
        {
            int a = 0, b = 0, c = 0;

            for (int idx = 0; idx < exp.a.size(); ++idx)
            {
                a = a * result + (exp.a[idx] - '0');
            }
            for (int idx = 0; idx < exp.b.size(); ++idx)
            {
                b = b * result + (exp.b[idx] - '0');
            }

            if (exp.oper == '+')
                c = a + b;
            else
                c = a - b;

            string res;

            if (c == 0)
            {
                res = "0";
            }
            else
            {
                while (c > 0)
                {
                    res += (c % result) + '0';
                    c /= result;
                }

                reverse(res.begin(), res.end());
            }

            if (result_str == "")
            {
                result_str = res;
            }
            else if (result_str != res)
            {
                same = false;
                break;
            }
        }

        if (same)
            ans += result_str;
        else
            ans += '?';

        answer.push_back(ans);
    }

    return answer;
}

코드가 길어졌지만 실력이 좋다면 짧아지겠네요