[PCCP 기출문제] 4번 [cpp]

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

---

알고리즘 : 진법 추론과 주어진 수식의 일관성 검증, 브루트 포스(완전 탐색)

핵심

• 모든 수에서 사용된 숫자 자릿수 확인
• 각 진법에 대해 모든 숫자의 자릿수가 해당 진법에서 유효한지 확인합니다.
• 알려진 수식들이 해당 진법에서 성립하는지 확인합니다.
• 가능한 진법이 여러 개인 경우, 각 진법에서 가능한 결괏값을 수집하여 동일한 결괏값이면 채우고, 그렇지 않으면 '?'를 사용합니다.

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

using namespace std;

// 주어진 문자열 숫자를 특정 진법(base)에서 10진수로 변환하는 함수
// 유효하지 않은 자릿수가 있으면 -1을 반환
int toDecimal(const string &numStr, int base) {
    int num = 0;
    for (char c : numStr) {
        // 문자가 숫자인지 확인
        if (!isdigit(c))
            return -1;
        int digit = c - '0';
        // 자릿수가 해당 진법에서 유효한지 확인
        if (digit >= base)
            return -1;
        num = num * base + digit;
    }
    return num;
}

// 10진수 숫자를 특정 진법(base)의 문자열로 변환하는 함수
string fromDecimal(int num, int base) {
    if (num == 0)
        return "0";
    string result = "";
    while (num > 0) {
        int digit = num % base;
        // 자릿수를 문자로 변환하여 앞에 추가
        result = char('0' + digit) + result;
        num /= base;
    }
    return result;
}

vector<string> solution(vector<string> expressions) {
    vector<string> answer;             // 최종 결과를 저장할 벡터
    vector<string> knownExpressions;   // 결과가 알려진 수식들
    vector<string> unknownExpressions; // 결과가 지워진 수식들
    set<string> allNumbers;            // 모든 수식에서 등장하는 숫자들

    // 수식들을 순회하며 파싱하고 숫자들을 수집
    for (string expr : expressions) {
        size_t pos = expr.find('=');           // '='의 위치 찾기
        string left = expr.substr(0, pos - 1); // 왼쪽 수식 (연산자 포함)
        string right = expr.substr(pos + 2);   // 오른쪽 결과 값 또는 'X'
        if (right == "X") {
            // 결과가 지워진 수식
            unknownExpressions.push_back(expr);
        } else {
            // 결과가 알려진 수식
            knownExpressions.push_back(expr);
        }

        // 수식에서 숫자 추출하여 수집
        istringstream iss(expr);
        string A_str, op, B_str, eq, C_str;
        iss >> A_str >> op >> B_str >> eq >> C_str;
        allNumbers.insert(A_str);
        allNumbers.insert(B_str);
        if (C_str != "X") {
            allNumbers.insert(C_str);
        }
    }

    set<int> possibleBases; // 가능한 진법들을 저장할 집합

    // 2진법부터 9진법까지 검사
    for (int base = 2; base <= 9; ++base) {
        bool isValidBase = true;
        // 모든 숫자의 자릿수가 해당 진법에서 유효한지 확인
        for (string numStr : allNumbers) {
            for (char c : numStr) {
                if (!isdigit(c)) { // 1. 숫자인지 확인
                    isValidBase = false;
                    break; // 숫자가 아니면 더 이상 검사할 필요가 없음
                }
                int digit = c - '0'; // 2. 문자를 숫자로 변환
                if (digit >= base) { // 3. 숫자가 진법에서 유효한지 확인
                    isValidBase = false;
                    break; // 진법에서 허용되지 않는 숫자면 더 이상 검사할 필요가 없음
                }
            }
            if (isValidBase == false)
                break;
        }
        if (isValidBase == false)
            continue; // 해당 진법은 제외

        // 알려진 수식들이 해당 진법에서 성립하는지 확인
        for (string expr : knownExpressions) {
            istringstream iss(expr);
            string A_str, op, B_str, eq, C_str;
            iss >> A_str >> op >> B_str >> eq >> C_str;
            int A = toDecimal(A_str, base);
            int B = toDecimal(B_str, base);
            int C = toDecimal(C_str, base);
            if (A == -1 || B == -1 || C == -1) {
                isValidBase = false;
                break; // 유효하지 않은 자릿수
            }
            int result = (op == "+") ? A + B : A - B;
            if (result != C) {
                isValidBase = false;
                break; // 수식이 성립하지 않음
            }
        }
        if (isValidBase) {
            // 해당 진법은 가능한 진법
            possibleBases.insert(base);
        }
    }

    // 가능한 진법이 없는 경우
    if (possibleBases.empty()) {
        // 모든 결괏값을 '?'로 채움
        for (string expr : unknownExpressions) {
            answer.push_back(expr.substr(0, expr.find('X')) + "?");
        }
        return answer;
    }

    // 가능한 진법이 하나인 경우
    if (possibleBases.size() == 1) {
        int base = *possibleBases.begin(); // 유일한 진법
        for (string expr : unknownExpressions) {
            istringstream iss(expr);
            string A_str, op, B_str, eq, C_str;
            iss >> A_str >> op >> B_str >> eq >> C_str;
            int A = toDecimal(A_str, base);
            int B = toDecimal(B_str, base);
            if (A == -1 || B == -1) {
                // 유효하지 않은 자릿수
                answer.push_back(expr.substr(0, expr.find('X')) + "?");
                continue;
            }
            int result = (op == "+") ? A + B : A - B;
            if (result < 0) {
                // 결과가 음수인 경우
                answer.push_back(expr.substr(0, expr.find('X')) + "?");
                continue;
            }
            string resultStr = fromDecimal(result, base);
            // 결과 자릿수가 유효한지 확인
            bool validDigits = true;
            for (char c : resultStr) {
                int digit = c - '0';
                if (digit >= base) {
                    validDigits = false;
                    break;
                }
            }
            if (!validDigits) {
                answer.push_back(expr.substr(0, expr.find('X')) + "?");
                continue;
            }
            // 결괏값 채우기
            answer.push_back(expr.substr(0, expr.find('X')) + resultStr);
        }
    } else {
        // 가능한 진법이 여러 개인 경우
        for (string expr : unknownExpressions) {
            istringstream iss(expr);
            string A_str, op, B_str, eq, C_str;
            iss >> A_str >> op >> B_str >> eq >> C_str;
            set<string> possibleResults; // 가능한 결과 값들
            bool validResultExists = false;
            for (int base : possibleBases) {
                int A = toDecimal(A_str, base);
                int B = toDecimal(B_str, base);
                if (A == -1 || B == -1) {
                    continue;
                }
                int result = (op == "+") ? A + B : A - B;
                if (result < 0) {
                    continue;
                }
                string resultStr = fromDecimal(result, base);
                // 결과 자릿수가 유효한지 확인
                bool validDigits = true;
                for (char c : resultStr) {
                    int digit = c - '0';
                    if (digit >= base) {
                        validDigits = false;
                        break;
                    }
                }
                if (!validDigits)
                    continue;
                validResultExists = true;
                possibleResults.insert(resultStr);
            }
            if (!validResultExists || possibleResults.empty()) {
                // 유효한 결과가 없는 경우
                answer.push_back(expr.substr(0, expr.find('X')) + "?");
            } else if (possibleResults.size() == 1) {
                // 가능한 결과가 하나인 경우
                string result = *possibleResults.begin();
                answer.push_back(expr.substr(0, expr.find('X')) + result);
            } else {
                // 가능한 결과가 여러 개인 경우
                answer.push_back(expr.substr(0, expr.find('X')) + "?");
            }
        }
    }

    return answer;
}

기법

문자열 파싱

ex [14 + 3 = 17]
string expr;
istringstream iss(expr);
string A_str, op, B_str, eq, C_str;
//       14     +       3      =      17
iss >> A_str >> op >> B_str >> eq >> C_str;

before [13 - 6 = X] -> after [13 - 6 = 5]
// expr [13 - 6 = X]에서 X를 찾고 expr에서 시작부터 0까지 자름.
// 그리고 resultstr [5] 값을 붙이면서 answer엣 [13 - 6 = 5] 할당
string answer = expr.substr(0, expr.find('X')) + resultStr;