[프로그래머스/C++] [PCCP 기출문제] 4번 / 수식 복원하기

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 크게 어렵지 않지만, 구현이 생각보다 빡센 문제였다.

 

주어진 수식들 중에 수식의 결과를 알고 있다면, 그 수식을 이용해 N진법이 가능한지 판단하고, 만약 결과를 모른다면 후보군에 두면 된다.

 

N진법이 가능한지 판단하는 방법은 간단하다.

 

먼저 2~9진법의 수로만 수식이 이루어지므로, A + B = C라는 수식에서 A, B, C를 각각 N진법의 수가 가능한지 판단한다.

만약 A, B, C 수가 전부 N진법이 가능하다면, A + B라는 값이 C라는 식과 일치하는지 판단한다.

 

이렇게 비교해서 만약 A+B=C라면 이 수식에서 N진법이 가능하다는 뜻이다.

만약 A+B값이 C와 다르다면 N진법은 현재 수식은 N진법이 아니라는 뜻이다.

 

이렇게 조건을 비교해 수식들로부터 2~9진법중 가능한 N진법 목록을 뽑는다.

 

이후 이 N진법 목록을 이용해 수식의 값을 모르는 식의 값을 구해보면된다.

 

예를 들어 가능한 N진법 List가 [3, 4, 5]라면, A+B 를 3진법으로 계산한 결과를 4진법으로 계산한결과, 5진법으로 계산한 결과와 비교한다.

 

이렇게 모든 진법으로 계산한 결과를 비교한 뒤, 모든 진법으로 계산했을 때, 같은 값 X가 나오면 X를 그 수로 표현하고 만약 하나라도 다른 값이 나오면 ?를 출력하면 된다.

 

이때 진법을 변환할 때, 헷갈리지 않게 주의해야 한다.

 

나는 계산을 편하게 하기 위해 A + B = C라는 수식이 있으면,  A, B, C를 2~9진법 수라고 가정하고 10진법의 값으로 변경했다.

 

이후 N진법 수 A, B, C를 10진법으로 변환한 뒤에 계산해 결과 값 A+B = C라면 N진법 이 가능하다고 판단했다.

 

반대로 X값을 구하는 과정은 좀 더 복잡하다.

 

A + B = X에서 A, B를 10진법으로 바꾼 뒤 A+B를 계산한다. 이후 A+B를 다시 N_0진법으로 변환한 수를 저장한다.

 

이후 가능한 N진법 List { N_0, N_1, N_2 ... } 에서  A+B를 다시 10진법으로 바꾼 뒤 A+B를 계산하고 A+B를 N_1진법으로 변환해 이전에 N_0진법으로 변환한 수와 비교했다.

 

이후 비교한 결과 값들이 전부 같은 수라면 X값을 그 수로 변환했다. 

 

 

​

[아이디어 정리]

1. 결과 값이 X가 아닌 식들을 이용해 가능한 N진법 List를 만든다.
2. 결과 값이 X였던 식들을 전부 N진법 List에 대해 숫자를 변환해 결과 값이 모두 같은 수로 표현되는지, 다른 값이 있어 ?로 표현되는지 판단한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <sstream>

using namespace std;
vector<string> StrSplit(string str){
    stringstream sst(str);
    string buf;
    vector<string>retV;
    while(getline(sst,buf,' ')){
        retV.push_back(buf);
    }
    return retV;
}


int convAtoB(int a, int b){ // 수 A(b)를 10진법으로
    int retN=0;
    int tt=1;
    while(a>0){
        if (a%10>=b){
            return -1;
        }
        retN+=(a%10)*tt;
        tt*=b;
        a/=10;
    }
    return retN;
}

int conv10toB(int a, int b){ //10진법 수 a를 b진법으로
    int retN=0;
    int tt=1;
    while(a>0){
        retN+=(a%b)*tt;
        tt*=10;
        a/=b;
    }
    return retN;
}

vector<int> notNLst(vector<string> str){
    int A,B,C;
    vector<int> retVi;
    for (int i=2; i<10; i++)
    {
        A=convAtoB(stoi(str[0]),i);
        B=convAtoB(stoi(str[2]),i);
        if (str[4]=="X"){
            if (A<0||B<0){
                retVi.push_back(i);
            }
        }
        else{
            C=convAtoB(stoi(str[4]),i);
            if (A<0||B<0||C<0){
                retVi.push_back(i);
                continue;
            }
            if (str[1]=="-")
            {
                if (A-B!=C)
                    retVi.push_back(i);
            }
            else
            {
                if (A+B!=C)
                    retVi.push_back(i);
            }
        }
    }
    return retVi;
}

vector<string> solution(vector<string> expressions) {
    vector<string> answer;
    vector<vector<string>> tmpAns;
    vector<bool>visit(10,true);
    for (int i=0; i<expressions.size(); i++){
        vector<string> tmpS=StrSplit(expressions[i]);
        if (tmpS[4]=="X"){
            tmpAns.push_back(tmpS);
        }
        vector<int> ti=notNLst(tmpS);
        for (int j=0; j<ti.size(); j++){
            visit[ti[j]]=false;
        }
    }
    vector<int> canList;
    for (int i=2; i<10; i++){
        if (visit[i])
        {
            canList.push_back(i);
        }
    }
    for (int i=0; i<tmpAns.size(); i++){
        int A,B,C, cmpC;
        bool flag=true;
        A=convAtoB(stoi(tmpAns[i][0]),canList[0]);
        B=convAtoB(stoi(tmpAns[i][2]),canList[0]);
        if (tmpAns[i][1]=="+")
        {
            C=conv10toB(A+B,canList[0]);
        }
        else{
            C=conv10toB(A-B,canList[0]);
        }
        for (int j=1; j<canList.size(); j++){
            A=convAtoB(stoi(tmpAns[i][0]),canList[j]);
            B=convAtoB(stoi(tmpAns[i][2]),canList[j]);
            if (tmpAns[i][1]=="+")
            {
                cmpC=conv10toB(A+B,canList[j]);
            }
            else{
                cmpC=conv10toB(A-B,canList[j]);
            }
            if (cmpC!=C){
                flag=false;
                tmpAns[i][4]="?";
                break;
            }
        }
        if (flag){
            tmpAns[i][4]=to_string(C);
        }
        string sss="";
        for (int j=0; j<4; j++){
            sss+=tmpAns[i][j]+" ";
        }
        sss+=tmpAns[i][4];
        answer.push_back(sss);
    }
    return answer;
}

---

 

프로그래머스에 새로 문제가 추가 돼서 풀어봤다.

단순한 문제지만, C++로 구현하다보니 생각보다 빡셌던 문제였다.

컴퓨터가 기본적으로 표현해주는 진법이 10진법이다보니 생각보다 많이 헷갈렸던 문제다.

이럴줄 알았으면 진법 변환이 아니라 n진법을 계산해 결과값을 string으로 표현해주는 함수를 만드는게 더 빨랐을 것 같다;;

 

프로그래머스