프로그래머스 문제 - 수식 복원하기

프로그래머스 수식 복원하기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

덧셈 혹은 뺄셈 수식이 여럭 개 적한 고대 유물이 있습니다.
이 문명이 사용하던 진법 체계가 10진법이 아니라는 것을 알아내었습니다.(2~9진법 중 한가지)
수식들 중 몇 개의 수식은 결과값이 지워져 있으며, 이 문명이 사용하던 진법에 맞도록 지워진 결괏값을 채워 넣으려 합니다.
결과값이 불확실한 수식은 결과 대신 ?를 채워서 수식을 완성시켜 줍니다.

문제 풀이

문제를 크게 보았을 때, 주어진 수식들 중 결과값이 있는 수식과 2~9진법을 맞춰보며 가능성이 있는 진법 체계를 확인 후 답을 구하면 될 것이라 보입니다.
처음으로 봐야 할 것은 N진법은 0~N-1 범위의 수만 사용이 가능하기 때문에 모든 수식들의 문자들 중 가장 큰 문자+1의 수가 가질 수 있는 진법의 최소가 됩니다.
그렇게 되면 진법의 최소값~9까지의 범위 내에서 계산하면 됩니다.

이후 진법의 최소값~9까지의 범위 내의 진법들을 검증하기 위해 결과값을 아는 수식들을 10진법으로 풀어낸 후 확인해봐야 합니다.
예를 들어 6~9진법을 검증하기 위해 각 수식을 6진법->10진법으로 변환 후 식 확인, 7진법->10진법으로 변환 후 식 확인 ->... 이런 식으로 진행하여 한번 더 가능성 있는 진법들을 찾아줍니다.

이후 걸러낸 가능성 있는 진법들을 결과값이 X인 수식에다 적용시켜 결과값들을 확인해줍니다.
이때, 결과값들이 전부 같다면 해당 결과값으로 식을 만들어 저장시켜 주면 되고, 다르면 결과가 불확실하다는 뜻이므로 ?로 채워 식을 만들어주면 됩니다.
결과값이 전부 같은지 확인하는 방법은 여러 가지가 있으며, 저는 hash테이블을 사용하여 찾아내었습니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int ChangeBinaryToNumber(int binary, string str)
{
    int sum = 0;
    int t = 1;
    for(int i = str.length()-1; i >= 0; i--)
    {
        sum += t * ((int)str[i] - 48);
        t *= binary;
    }
    return sum;
}

string ChangeNumberToBinary(int binary, int num)
{
    if(num == 0)
        return "0";
    
    string str = "";
    int t = binary * binary;  
    for(int i = 0; i < 3; i++)
    {
        int n = num / t;
        if(n != 0 || n == 0 && str != "")
            str = str + to_string(n);
        num = num % t;        
        t /= binary;
    }
    return str;
}

vector<string> solution(vector<string> expressions) {
    vector<string> answer;
    vector<vector<string>> str(100, vector<string>());
    int index = 0;
    vector<int> binaryNumbers;
    char maxNum = 2;
    
    //수식 나누기
    for(string s : expressions)
    {
        char ch[s.length()];
        strcpy(ch, s.c_str());
        char *ptr = strtok(ch, " =");
        while(ptr != NULL)
        {
            str[index].push_back(string(ptr));
            ptr = strtok(NULL, " =");
        }
        index++;
    }
    
    //가능한 진법의 최소 수 계산
    for(int i = 0; i < expressions.size(); i++)
    {
        for(int j = 0; j < str[i].size(); j++)
        {
            if(str[i][j] != "X" && str[i][j] != "+" && str[i][j] != "-")
            {
                for(int k = 0; k < str[i][j].length(); k++)
                    if(maxNum < str[i][j][k])
                        maxNum = str[i][j][k];
            }
        }
    }
    maxNum++;
    cout << maxNum << endl;
    
    int cnt = 0;
    
    //완성된 수식들을 확인하여 가능한 진법 찾기
    for(int binary = ((int)maxNum - 48); binary <= 9; binary++)
    {
        for(int i = 0; i < expressions.size(); i++)
        {
            cnt++;
            if(str[i][3] == "X")
                continue;
            
            if(str[i][1] == "+")
            {
                if(ChangeBinaryToNumber(binary, str[i][0]) + ChangeBinaryToNumber(binary, str[i][2]) != ChangeBinaryToNumber(binary, str[i][3]))
                {
                    cnt--;
                    break;
                }
            }
            else
            {
                if(ChangeBinaryToNumber(binary, str[i][0]) - ChangeBinaryToNumber(binary, str[i][2]) != ChangeBinaryToNumber(binary, str[i][3]))
                {
                    cnt--;
                    break;
                }
            }
        }
        
        if(cnt == expressions.size())
        {
            binaryNumbers.push_back(binary);
        }
        cnt = 0;
    }
    
    //X값 계산 후 저장
    unordered_map<string, int> m;
    unordered_map<string, int>::iterator iter;
    string s;
    
    for(int i = 0; i < expressions.size(); i++)
    {
        if(str[i][3] != "X")
            continue;
        for(int j = 0; j < binaryNumbers.size(); j++)
        {
            int binary = binaryNumbers[j];
            int val;
            if(str[i][1] == "+")
            {
                val = ChangeBinaryToNumber(binary, str[i][0]) + ChangeBinaryToNumber(binary, str[i][2]);
                s = ChangeNumberToBinary(binary, val);
            }
            else
            {
                val = ChangeBinaryToNumber(binary, str[i][0]) - ChangeBinaryToNumber(binary, str[i][2]);
                s = ChangeNumberToBinary(binary, val);
            }
            if(m.find(s) == m.end())
            {
                m.insert({s, binary});
            }
        }
        if(m.size() == 1)
        {
            iter = m.begin();
            s = str[i][0] + " " + str[i][1] + " " + str[i][2] + " = " + iter->first;
            answer.push_back(s);
        }
        else
        {
            s = str[i][0] + " " + str[i][1] + " " + str[i][2] + " = ?";
            answer.push_back(s);
        }
        m.clear();
    }
    
    return answer;
}

출저

https://school.programmers.co.kr/learn/courses/30/lessons/340210