[Javascript] 프로그래머스 - 수식 복원하기

문제 설명

고대 문명의 유물에서 발견된 덧셈과 뺄셈 수식을 분석하여, 해당 문명이 사용한 진법을 찾아야 합니다. 주어진 수식 중 일부는 결과 값이 지워져 있으며, 해당 수식들의 결괏값을 복원해야 합니다.

진법은 2진법부터 9진법 사이이며, 수식들에서 사용된 숫자를 통해 사용된 진법을 유추할 수 있습니다. 결괏값이 확정적으로 결정되지 않는 경우에는 ?로 표시해야 합니다.

---

제한 사항

• 2 ≤ expressions의 길이 ≤ 100
• 수식은 "A + B = C" 혹은 "A - B = C" 형태의 문자열입니다.
• A, B는 두 자릿수 이하의 정수이며, C는 세 자릿수 이하의 정수 또는 X(지워진 값)입니다.
• 진법 내에서 수식이 성립하도록 보장됩니다.

---

해결 방법

알고리즘: 비트마스킹, 진법 변환

1. 가능한 진법 유추
   • 수식에 등장하는 모든 숫자를 분석하여, 사용할 수 없는 진법을 제외합니다.
   • 예를 들어, 숫자 8이 등장했다면 2~7진법은 제외됩니다.
   • 이를 비트마스킹을 활용하여 처리합니다.
2. 진법 검증
   • 각 수식을 2진법부터 9진법으로 변환하여 계산한 후, 결과 값이 일치하지 않는 경우 해당 진법을 제외합니다.
   • 즉, A + B = C 또는 A - B = C가 주어진 진법에서 성립하지 않으면 해당 진법을 배제합니다.
3. 결괏값 복원
   • 결과 값이 지워진(X) 수식의 경우, 남은 후보 진법에서 계산한 값이 유일하면 해당 값을 사용합니다.
   • 서로 다른 진법에서 결과가 다르면 ?로 대체합니다.

---

시간 복잡도

• 가능한 진법 유추: O(N)
• 진법 검증: O(N)
• 결괏값 복원: O(N)
• 전체 시간 복잡도: O(N)

---

구현 코드

function solution(expressions) {
  let answer = [];
  let bit = 0b10000000011;
  const fullBit = 0b1111111111;
  let list = [];

  for (const expression of expressions) {
    const [a, op, b, _, value] = expression.split(" ");

    if (value === "X") {
      list.push([a, op, b]);
    }

    let [num1, num2, num3] = [a, b, value === "X" ? 0 : value].map(Number);

    [num1, num2, num3].forEach((num) => {
      num
        .toString()
        .split("")
        .forEach((digit) => {
          bit |= fullBit >> (9 - Number(digit));
        });
    });

    if (value === "X") continue;

    for (let i = 2; i <= 9; ++i) {
      if (bit & (1 << i)) continue;

      let calcValue =
        op === "+" ? parseInt(a, i) + parseInt(b, i) : parseInt(a, i) - parseInt(b, i);

      if (value !== calcValue.toString(i)) {
        bit |= 1 << i;
      }
    }
  }

  for ([a, op, b] of list) {
    let prevValue = null;
    let isInconsistent = false;
    for (let i = 2; i <= 9; ++i) {
      if (bit & (1 << i)) {
        continue;
      }

      let nextValue =
        op === "+"
          ? (parseInt(a, i) + parseInt(b, i)).toString(i)
          : (parseInt(a, i) - parseInt(b, i)).toString(i);

      if (prevValue !== null && prevValue !== nextValue) {
        isInconsistent = true;
        break;
      }

      prevValue = nextValue;
    }

    answer.push(`${a} ${op} ${b} = ${isInconsistent ? "?" : prevValue}`);
  }

  return answer;
}