Problem SolvingJul 7, 2026

[프로그래머스] 340210 [PCCP 기출문제] 4번 / 수식 복원하기 (JavaScript)

#Problem Solving#Coding Test#Algorithm#Programmers#340210#JavaScript#Parsing#Implementation#Brute Force
[프로그래머스] 340210 [PCCP 기출문제] 4번 / 수식 복원하기 (JavaScript)

문제

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



풀이

수식의 최대 개수는 100100개, 수식의 최대 길이는 1313이므로, brute-force로 가능한 모든 진법을 계산해도 충분히 시간 내에 해결할 수 있다.

따라서 시간 복잡도는 고려하지 않기로 하고, tokenize, parse 과정을 통해 수식을 계산 가능한 형태로 변환하고, 진법 계산을 통해 가능한 해를 찾는 것에 집중했다.

다만, 문제가 친절해서 수식은 특정한 형태가 고정되어있어 tokenize도 직접 구현할 필요 없이 split으로 간단히 구현할 수 있었고, parse 과정도 마찬가지로 구현할 필요가 없었다.

진법 계산 로직이라도 직접 짜볼까 했지만, parseInt와 toString을 활용해 간단히 구현했다.

테스트케이스도 친절해서 딱히 생각할 거리가 많지는 않은 문제인 것 같다.



소스 코드

javascript
const evaluateInBase = (a, op, b, base) => parseInt(a, base) + (1 - 2 * (op === "-")) * parseInt(b, base);

const isValidInBase = (tokens, base) => {
    const [ a, op, b, _, c ] = tokens;
    
    for (const number of [ a, b, c ]) {
        if (number === "X") {
            return true;
        }
        for (const ch of number) {
            if (base <= Number(ch)) {
                return false;
            }
        }
    }
    
    return evaluateInBase(a, op, b, base) === parseInt(c, base);
}

const findValidBases = (tokenized) => {
    const ret = [];

    for (let base = 2; base <= 9; base++) {
        if (tokenized.every((tokens) => isValidInBase(tokens, base))) {
            ret.push(base);
        }
    }

    return ret;
}

const solution = (expressions) => {
    const tokenized = expressions.map((expression) => expression.split(" "));
    const candidates = findValidBases(tokenized);
    
    return tokenized
        .filter((tokens) => tokens[4] === "X")
        .map((tokens) => {
            let result = undefined;
            const [ a, op, b, _, c ] = tokens;
        
            for (const candidate of candidates) {
                const value = evaluateInBase(a, op, b, candidate).toString(candidate);
                
                if (result && result !== value) {
                    result = "?";
                    break;
                }
                result = value;
            }
        
            return [ a, op, b, _, result ].join(" ");
        });
}

Share this post

N