[programmers/js] [PCCP 기출문제] 4번 / 수식 복원하기

[PCCP 기출문제] 4번 / 수식 복원하기

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

문제 설명

덧셈 혹은 뺄셈 수식이 여러 개 적힌 고대 문명의 유물을 찾았습니다. 이 수식들 중 일부는 결괏값이 지워져 있으며, 해당 수식을 통해 사용된 진법을 맞추어 결괏값을 채워 넣어야 합니다. 수식들은 "A + B = C" 또는 "A - B = C" 형태이며, C가 "X"로 표시된 수식은 결괏값이 지워진 것입니다. 이러한 수식들의 결괏값을 채워 넣는 문제입니다.

풀이

1. 최소 진법 계산
   각 수식에 등장하는 숫자들 중 가장 큰 숫자에서 진법을 추론합니다. 진법은 최소 2 이상이며, 각 수식에서 등장하는 숫자 중 가장 큰 숫자에 맞춰 최소 진법을 결정합니다. 예를 들어, 수식에 "13"이라는 숫자가 등장하면 최소 4진법 이상이어야 합니다.

2. 가능한 진법들 확인
   2진법부터 9진법까지 각 진법에 대해 수식이 유효한지를 확인합니다. 유효한 진법을 찾기 위해 각 수식에 대해 "+" 혹은 "-" 연산을 처리하고, 결과가 일치하는지 체크합니다.

3. 결과 채우기
   "X"로 표시된 값에 대해 유효한 진법에 따라 계산한 값을 채워 넣습니다. 만약 여러 진법에서 가능한 값이 다르다면 ?로 표시하고, 하나의 값만 가능하면 해당 값을 넣습니다.

function solution(expressions) {
    // 가능한 진법 찾기
    let minBase = 2;
    expressions.forEach(expr => {
        const numbers = expr.match(/\d+/g)?.map(Number) || [];
        minBase = Math.max(minBase, ...numbers.map(n => Math.max(...n.toString().split('').map(Number)) + 1));
    });
    
    let validBases = new Set();
    for (let base = minBase; base <= 9; base++) {
        if (expressions.every(expr => validateBase(expr, base))) {
            validBases.add(base);
        }
    }
    
    // 결과 채우기
    const result = [];
    expressions.forEach(expr => {
        if (!expr.includes("X")) return;
        
        let possibleValues = new Set();
        for (const base of validBases) {
            const value = computeValue(expr, base);
            if (value !== null) possibleValues.add(value);
        }
        
        const finalValue = possibleValues.size === 1 ? [...possibleValues][0] : "?";
        result.push(expr.replace("X", finalValue));
    });
    
    return result;
}

function validateBase(expression, base) {
    const [left, right] = expression.split("=").map(s => s.trim());
    const [a, op, b] = left.split(" ");
    const c = right;
    
    if (c === "X") return true; // X가 있으면 계산 스킵
    
    const numA = parseInt(a, base);
    const numB = parseInt(b, base);
    const numC = parseInt(c, base);
    
    return op === "+" ? (numA + numB === numC) : (numA - numB === numC);
}

function computeValue(expression, base) {
    const [left, right] = expression.split("=").map(s => s.trim());
    const [a, op, b] = left.split(" ");
    
    const numA = parseInt(a, base);
    const numB = parseInt(b, base);
    
    if (right === "X") {
        const result = op === "+" ? numA + numB : numA - numB;
        return result.toString(base);
    }
    return null;
}