프로그래머스[Lv.3] - 수식 복원하기

 

 

문제 설명

당신은 덧셈 혹은 뺄셈 수식이 여러 개 적힌 고대 문명의 유물을 찾았습니다. 이 수식들을 관찰하던 당신은 이 문명이 사용하던 진법 체계가 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 함수를 완성해 주세요.

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

---

 

 

 

 

 

 

제한 사항

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

 

---

 

 

 

 

 

 

풀이

문제를 요약하면, 수식이 여러 개 주어지면 해당 수식을 이용하여 X로 표시된 부분을 정할 수 있다면 수를 출력하고 정할 수 없다면 ?를 출력하는 것이다.

단, 수식은 2~9진법 중 하나이다.

 

문제를 풀기위해서는 두 가지를 해결해야 한다.

• n진법인지 판단하기
• n진법으로 계산하기

우선, n진법을 판단하는 방법은 2~9 진법 중 하나를 가정하고 X가 포함되지 않은 식이 유효한지 판단하면 된다.

그전에 몇 개 거를 수 있는데, 바로 n진법에서는 n이상의 수는 표현할 수 없다는 것이다.

즉, 수식을 살펴보며 최댓값이 k라고 한다면 k+1 진법 이상만 가능하다는 뜻이다.

void CheckDigit(string num)
{
    for(auto c : num)
    {
        int digit = c - '0';
        while(digit > 1)
        {
            possible[digit--] = false;
        }
    }
}

 

이제 식을 둘러보며 가능 여부를 판단하면 된다.

가능 여부를 판단하는 조건은 n진법을 가정하고 계산한 결과가 X가 아닌 식에서 동일한 결과가 나온다면 n진법은 가능성이 존재하는 것이다.

예를 들어 보자.

["14 + 3 = 17", "13 - 6 = X", "51 - 5 = 44"]

이러한 입력이 있을 때 숫자를 살펴보면 가능한 진법은 8, 9밖에 없다.

8진법이라 가정했을 때, 14+3 = 17이 맞기 때문에 가능하다. 51 - 5 같은 경우에는 8진법이라 하면 44가 맞다.

하지만, 9진법이라면 45가 된다.

따라서, 가능한 경우는 8진법밖에 존재하지 않는다.

그렇다면 ?를 출력하는 경우는 X가 아닌 경우가 모두 맞지만 X인 경우에서 답이 여러 개가 나왔을 경우이다.

즉, n진법과 계산 결과를 모두 저장하여 결과가 같은지 판단하면 답을 구할 수 있다.

 

그럼 이제 n진법을 계산하는 방법을 알아보자.

n진법을 계산하려면 +, - 두 가지 연산을 정의해야 한다. 

+의 경우에는 끝자리부터 더해 n이상이 되면 한 자리 올려주면 된다.

그리고 마지막에 올라간 자리까지 계산해주면 된다.

int Plus(string a, string b, int d)
{
    int result = 0;
    int carry = 0;
    
    int aLen = a.length();
    int bLen = b.length();
    
    for(int i = 0; i < max(aLen, bLen); i++)
    {
        int aNum = 0;
        int bNum = 0;
        if(i < aLen) aNum = a[aLen - i - 1] - '0';
        if(i < bLen) bNum = b[bLen - i - 1] - '0';
        int sum = aNum + bNum + carry;
        carry = 0;
        
        int rest = sum % d;
        carry += sum / d;
        
        result += rest * pow(10, i);
    }
    
    if(carry != 0) result += carry * pow(10, max(aLen, bLen));
    
    return result;
}

 

-의 경우에도 마찬가지로 끝자리부터 빼가면 된다.

만약 빼려는 수가 더 크다면 앞에서 n만큼 가져오면 된다.

int Minus(string a, string b, int d)
{
    int result = 0;
    int carry = 0;
    
    int aLen = a.length();
    int bLen = b.length();
    
    for(int i = 0; i < max(aLen, bLen); i++)
    {
        int aNum = 0;
        int bNum = 0;
        if(i < aLen) aNum = a[aLen - i - 1] - '0';
        if(i < bLen) bNum = b[bLen - i - 1] - '0';
        
        int sum = (aNum - carry) - bNum;
        carry = 0;
        
        if(sum < 0)
        {
            carry++;
            sum += d;
        }
        
        result += sum * pow(10, i);
    }
    
    return result;
}

 

이러한 연산의 편의를 위해 식을 구조체로 나타내었다.

struct Expr
{
    string num1, num2;
    bool bPlus;
    string result;
    int i;
    
    int Matching(int d)
    {
        int tempResult;
        if(bPlus) tempResult = Plus(num1, num2, d);
        else tempResult = Minus(num1, num2, d);
        
        if(result != "X")
        {
            if(tempResult == stoi(result)) return tempResult;
            return INVALID;
        }
        else
        {
            return tempResult;
        }
    }
    
    string Print()
    {
        string op = bPlus ? " + " : " - ";
        
        int r = INVALID;
        bool p = true;
        
        for(int j = 2; j < 10; j++)
        {
            if(!possible[j]) continue;
            
            if(r == INVALID)
            {
                r = answerList[i][j];
                continue;
            }
            
            if(r != answerList[i][j] && answerList[i][j] != INVALID)
            {
                p = false;
                break;
            }
        }
        
        if(!p) return num1 + op + num2 + " = ?";
        return num1 + op + num2 + " = " + to_string(r); 
    }
};

---

 

 

 

 

 

전체 코드

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

using namespace std;

const int INVALID = 1234567;
vector<bool> possible(10, true);
vector<vector<int>> answerList;

int Plus(string a, string b, int d)
{
    int result = 0;
    int carry = 0;
    
    int aLen = a.length();
    int bLen = b.length();
    
    for(int i = 0; i < max(aLen, bLen); i++)
    {
        int aNum = 0;
        int bNum = 0;
        if(i < aLen) aNum = a[aLen - i - 1] - '0';
        if(i < bLen) bNum = b[bLen - i - 1] - '0';
        int sum = aNum + bNum + carry;
        carry = 0;
        
        int rest = sum % d;
        carry += sum / d;
        
        result += rest * pow(10, i);
    }
    
    if(carry != 0) result += carry * pow(10, max(aLen, bLen));
    
    return result;
}

int Minus(string a, string b, int d)
{
    int result = 0;
    int carry = 0;
    
    int aLen = a.length();
    int bLen = b.length();
    
    for(int i = 0; i < max(aLen, bLen); i++)
    {
        int aNum = 0;
        int bNum = 0;
        if(i < aLen) aNum = a[aLen - i - 1] - '0';
        if(i < bLen) bNum = b[bLen - i - 1] - '0';
        
        int sum = (aNum - carry) - bNum;
        carry = 0;
        
        if(sum < 0)
        {
            carry++;
            sum += d;
        }
        
        result += sum * pow(10, i);
    }
    
    return result;
}

struct Expr
{
    string num1, num2;
    bool bPlus;
    string result;
    int i;
    
    int Matching(int d)
    {
        int tempResult;
        if(bPlus) tempResult = Plus(num1, num2, d);
        else tempResult = Minus(num1, num2, d);
        
        if(result != "X")
        {
            if(tempResult == stoi(result)) return tempResult;
            return INVALID;
        }
        else
        {
            return tempResult;
        }
    }
    
    string Print()
    {
        string op = bPlus ? " + " : " - ";
        
        int r = INVALID;
        bool p = true;
        
        for(int j = 2; j < 10; j++)
        {
            if(!possible[j]) continue;
            
            if(r == INVALID)
            {
                r = answerList[i][j];
                continue;
            }
            
            if(r != answerList[i][j] && answerList[i][j] != INVALID)
            {
                p = false;
                break;
            }
        }
        
        if(!p) return num1 + op + num2 + " = ?";
        return num1 + op + num2 + " = " + to_string(r); 
    }
};

vector<Expr> exprs;

void CheckDigit(string num)
{
    for(auto c : num)
    {
        int digit = c - '0';
        while(digit > 1)
        {
            possible[digit--] = false;
        }
    }
}

vector<string> solution(vector<string> expressions) {
    vector<string> answer;
    
    answerList.resize(expressions.size(), vector<int>(10, INVALID));
    
    possible[0] = false;
    possible[1] = false;
    
    for(int i = 0 ; i < expressions.size(); i++)
    {
        auto& expression = expressions[i];
        istringstream iss(expression);
        string buffer;
        
        vector<string> splited;
        while(getline(iss, buffer, ' '))
        {
            splited.push_back(buffer);
        }
        
        exprs.push_back({splited[0], splited[2], splited[1] == "+", splited[4], i});
        
        CheckDigit(splited[0]);
        CheckDigit(splited[2]);
        
        if(splited[4] != "X")
        {
            CheckDigit(splited[4]);
        }
    }
    
    
    for(int i = 0; i < exprs.size(); i++)
    {
        for(int j = 2; j < 10; j++)
        {
            if(!possible[j]) continue;
            answerList[i][j] = exprs[i].Matching(j);
            
            if(exprs[i].result != "X" && answerList[i][j] != stoi(exprs[i].result))
            {
                possible[j] = false;
                continue;
            }
        }
    }
    
    for(auto& expr : exprs)
    {
        if(expr.result != "X") continue;
        answer.push_back(expr.Print());
    }
    
    return answer;
}

---