알고리즘/programmers

[Programmers] 수식 복원하기

꾸준함. 2024. 10. 6. 21:53

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/340210

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

가능한 진법은 2 ~ 9진법이기 때문에 단순 구현으로 풀 수 있었던 문제였습니다.

 

#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <set>
using namespace std;
bool isValidNumber(const string& num, int base)
{
for (char c : num)
{
if (c < '0' || c > '9')
{
return false;
}
int digit = c - '0';
if (digit >= base)
{
return false;
}
}
return true;
}
int convertToDecimal(const string& num, int base)
{
int decimalNumber = 0;
for (char c : num)
{
int digit = c - '0';
decimalNumber = decimalNumber * base + digit;
}
return decimalNumber;
}
string convertFromDecimal(int number, int base)
{
if (number == 0)
{
return "0";
}
string result = "";
while (number > 0)
{
int digit = number % base;
result += (char)('0' + digit);
number /= base;
}
reverse(result.begin(), result.end());
return result;
}
vector<string> solution(vector<string> expressions) {
vector<string> answer;
vector<string> knownExpressions;
vector<pair<int, string>> missingExpressions;
int maxDigitUsed = 0;
for (int i = 0; i < expressions.size(); i++)
{
string expr = expressions[i];
for (char c : expr)
{
if (c >= '0' && c <= '9')
{
int digit = c - '0';
if (digit > maxDigitUsed)
{
maxDigitUsed = digit;
}
}
}
stringstream ss(expr);
string operand1, op, operand2, equalSign, result;
ss >> operand1 >> op >> operand2 >> equalSign >> result;
if (result == "X")
{
missingExpressions.push_back({i, expr});
}
else
{
knownExpressions.push_back(expr);
}
}
int minBase = max(maxDigitUsed + 1, 2);
vector<int> possibleBases;
for (int base = minBase; base <= 9; base++)
{
bool isValidBase = true;
for (const string expr : knownExpressions)
{
for (char c : expr)
{
if (c >= '0' && c <= '9')
{
int digit = c - '0';
if (digit >= base)
{
isValidBase = false;
break;
}
}
}
if (!isValidBase)
{
break;
}
stringstream ss(expr);
string operand1, op, operand2, equalSign, result;
ss >> operand1 >> op >> operand2 >> equalSign >> result;
if (!isValidNumber(operand1, base)
|| !isValidNumber(operand2, base)
|| !isValidNumber(result, base))
{
isValidBase = false;
break;
}
int num1 = convertToDecimal(operand1, base);
int num2 = convertToDecimal(operand2, base);
int res = convertToDecimal(result, base);
if (op == "+")
{
if (num1 + num2 != res)
{
isValidBase = false;
break;
}
}
else if (op == "-")
{
if (num1 - num2 != res)
{
isValidBase = false;
break;
}
}
else
{
isValidBase = false;
break;
}
}
if (isValidBase)
{
possibleBases.push_back(base);
}
}
for (const auto [index, expr] : missingExpressions)
{
stringstream ss(expr);
string operand1, op, operand2, equalSign, result;
ss >> operand1 >> op >> operand2 >> equalSign >> result;
set<string> possibleResults;
for (int base : possibleBases)
{
bool digitsValid = true;
for (char c : operand1 + operand2)
{
if (c >= '0' && c <= '9')
{
int digit = c - '0';
if (digit >= base)
{
digitsValid = false;
break;
}
}
}
if (!digitsValid)
{
continue;
}
if (!isValidNumber(operand1, base)
|| !isValidNumber(operand2, base))
{
continue;
}
int num1 = convertToDecimal(operand1, base);
int num2 = convertToDecimal(operand2, base);
int res = 0;
if (op == "+")
{
res = num1 + num2;
}
else if (op == "-")
{
res = num1 - num2;
if (res < 0)
{
continue;
}
}
else
{
continue;
}
string resStr = convertFromDecimal(res, base);
bool resultDigitsValid = true;
for (char c : resStr)
{
if (c >= '0' && c <= '9')
{
int digit = c - '0';
if (digit >= base)
{
resultDigitsValid = false;
break;
}
}
}
if (!resultDigitsValid)
{
continue;
}
possibleResults.insert(resStr);
}
string filledExpression = operand1 + " " + op + " " + operand2 + " = ";
if (possibleResults.size() == 1)
{
filledExpression += *possibleResults.begin();
}
else
{
filledExpression += "?";
}
answer.push_back(filledExpression);
}
return answer;
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~

반응형