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

프로그래머스

당신은 고대 문명의 유물을 찾았습니다. 유물에는 여러 수식들이 적혀있습니다. 수식들 중 몇 개의 수식에 결과값이 지워져 있을 때, 이 문명이 사용하던 진법에 맞도록 지워진 결괏값을 채워주세요. (2~9진법 중 하나)

 

풀이 방법

우선 사용 가능한 진법을 찾아야합니다. (여러개일 수 있습니다.)

3진법은 0~2, 8진법은 0~7까지의 수를 사용합니다. 즉, 수식들 중 가장 큰 수를 찾고 +1을 한 진법부터 탐색하면 되겠습니다.

set<int> questions;
set<int> bases;

int start = 2;
for (int i = 0; i < expressions.size(); i++)
{
    string& exprs = expressions[i];
    // 결과가 지워진 수식은 따로 index정보를 저장
    if (exprs.back() == 'X')
        questions.insert(i);

    for (char c : exprs)
    {
        if (c >= '2' && c <= '9'){
            start = max(start, (c-'0')+1);
        }
    }
}

for (int i = start; i <= 9; i++)
    bases.insert(i);

 

 

결과가 지워지지 않은 수식에 사용할 수 있는 모든 진법을 사용해보며 실제 결과값과 수식의 결과값이 일치하는지 확인합니다.

일치하지 않다면 해당 진법은 지웁니다.

for (int base : bases)
{
    for (int i = 0; i < expressions.size(); i++)
    {
    	// 결과가 지워진 수식이라면 건너뛰기
        if (questions.find(i) != questions.end())
            continue;

        string& exprs = expressions[i];
        int a, b, result; bool isPlus;
        // string 수식을 int로 불러오기
        Parsing(exprs, a, b, result, isPlus);

    // 실제 결과와 수식의 결과가 같다면 true를 반환함
        if (!Compute(a, b, result, base, isPlus))
        {
            bases.erase(base);
            break;
        }
    }       
}

 

 

살아남은 진법들과, 결과가 지워진 수식들을 비교하여 풀이합니다.

모든 진법에서 같은 정답이 나온다면 해당 결과를 표기,

다른 정답이 나온다면 '?'로 표기

vector<string> answer;
for (int q : questions)
{
    set<int> results;
    string& exprs = expressions[q];

    for (int base : bases)
    {
        int a, b, result; bool isPlus;
        Parsing(exprs, a, b, result, isPlus);
        Compute(a, b, result, base, isPlus);
        results.insert(result);
    }

    if (results.size() > 1)
        exprs[exprs.size()-1] = '?';
    else
    {
        exprs.pop_back();
        exprs += to_string(*results.begin());
    }

    answer.push_back(exprs);
}

return answer;

 

 

정답 코드

#include <string>
#include <vector>
#include <iostream>
#include <set>

using namespace std;

bool Compute(int a, int b, int& result, int base, bool plus)
{
    int thirdDigit = 0;
    int secondDigit = (a / 10) + (b / 10);
    int firstDigit = (a % 10) + (b % 10);

    if (plus)
    {
        if (firstDigit / base > 0)
        {
            secondDigit++;
            firstDigit -= base;        
        }

        if (secondDigit / base > 0)
        {
            thirdDigit++;
            secondDigit -= base;
        }
    }
    else
    {
        secondDigit = (a / 10) - (b / 10); // 무조건 0보다 큼
        firstDigit = (a % 10) - (b % 10); 
        if (firstDigit < 0){
            secondDigit--;
            firstDigit = (firstDigit % base + base) % base;            
        }
    }
    
    int total = thirdDigit*100 + secondDigit*10 + firstDigit;
    char p = plus ? '+' : '-';
    
    if (result == -1)
        result = total;
    
    return total == result;
}

void Parsing(string& exprs, int& a, int& b, int& result, bool& plus)
{
    a = exprs[0] -'0'; 
    int next = 2;

    if (exprs[1] != ' '){
        a = a * 10 + exprs[1] - '0';
        next++;                
    }

    plus = false;
    if (exprs[next] == '+')
        plus = true;

    next += 2;

    b = exprs[next] - '0';
    if (exprs[next+1] != ' '){
        b = b * 10 + exprs[next+1]-'0';
        next++;  
    }

    next += 4;

    result = exprs[next] - '0';
    if (exprs[next] == 'X')
        result = -1;
    
    next++;
    while (next < exprs.size())
    {
        result = result*10 + exprs[next]-'0';
        next++;
    }
}

vector<string> solution(vector<string> expressions) {
    set<int> questions;
    set<int> bases;
    
    int start = 2;
    // 진법 범위 찾기
    for (int i = 0; i < expressions.size(); i++)
    {
        string& exprs = expressions[i];
        
        if (exprs.back() == 'X')
            questions.insert(i);
        
        for (char c : exprs)
        {
            if (c >= '2' && c <= '9'){
                start = max(start, (c-'0')+1);
            }
        }
    }
    
    for (int i = start; i <= 9; i++)
        bases.insert(i);
    
    // 맞는 진법 찾기
    for (int base : bases)
    {
        for (int i = 0; i < expressions.size(); i++)
        {
            // 문제면 패스
            if (questions.find(i) != questions.end())
                continue;
            
            string& exprs = expressions[i];
            int a, b, result; bool isPlus;
            Parsing(exprs, a, b, result, isPlus);
            
            if (!Compute(a, b, result, base, isPlus))
            {
                bases.erase(base);
                break;
            }
        }       
    }
    
    // 살아남은 진법들과, 문제들을 비교하여 풀이
    // 모든 진법에서 같은 정답이 나오면 표기,
    // 다른 정답이 나오면 '?'로 정답 표기
    vector<string> answer;
    for (int q : questions)
    {
        set<int> results;
        string& exprs = expressions[q];
         
        for (int base : bases)
        {
            int a, b, result; bool isPlus;
            Parsing(exprs, a, b, result, isPlus);
            Compute(a, b, result, base, isPlus);
            results.insert(result);
        }
        
        if (results.size() > 1)
            exprs[exprs.size()-1] = '?';
        else
        {
            exprs.pop_back();
            exprs += to_string(*results.begin());
        }
        
        answer.push_back(exprs);
    }
    
    return answer;
}