문제 이해하기
숫자들이 나열되어 있을 때, 숫자 사이에 적절한 연산자(+, -, *, /, ^, %)와 등호(=)를 넣어 성립하는 등식을 완성하는 JavaScript 함수를 작성해야 합니다.
예를 들어 다음과 같습니다.
입력 : 5 3 8 출력 : 5+3=8 입력 : 9 27 3 출력 : 9=27/3 입력 : 5 2 25 , 1 5 2 출력 : 5^2=25 , 1=5%2
모든 입력에는 최소 한 가지 이상의 올바른 조합이 반드시 존재하며, 함수는 그중 하나만이라도 정확하게 성립하는 식을 반환하면 됩니다.
풀이 접근 방법
이 문제를 해결하기 위한 기본적인 알고리즘은 다음과 같습니다.
먼저 양쪽 중 더 큰 숫자를 등호의 한쪽에 배치합니다. 예를 들어 1 4 7이라면 7이 가장 크므로 등호의 오른쪽에 놓습니다.
그다음 등호를 가운데 숫자 앞에 배치합니다. 즉, 1 4 7은 1 4=7 형태가 됩니다.
남은 자리에 연산자를 채워 넣어 식이 실제로 성립하는지 검증합니다.
성립하지 않는다면 다른 숫자를 기준으로 삼아 같은 과정을 반복합니다.
실제 구현에서는 모든 경우를 시도하는 브루트 포스(brute force) 방식이 효과적입니다. 각 공백 위치마다 후보 연산자 목록에서 하나를 무작위로 삽입한 뒤, eval로 식을 평가하여 참(true)이 되는 첫 번째 조합을 정답으로 채택합니다. 이때 일반적인 비교를 위해 등호(=)는 ===로, 거듭제곱 기호(^)는 JavaScript의 ** 연산자로 치환한 후 평가합니다.
예제 코드
const arr = ['5 3 8', '9 27 3', '5 2 25', '1 5 2', '3 3 3 30'];
const findCombination = (arr = []) => {
const answers = [];
for(let i = 0; i < arr.length; i++){
const el = arr[i];
// 브루트 포스로 가능한 조합을 시도합니다
for(let n = 0; n < 1000; n++){
const s = el.replace(/ /g, () => '+-*/^%='[Math.floor(Math.random() * 7)]);
if(eval(s.replace(/=/g, '===').replace(/\^/g, '**')) === true
&& answers.indexOf(s) === -1){
answers.push(s);
}
}
}
return answers;
};
console.log(findCombination(arr));여기서 문자열 '+-*/^%='는 7개의 후보 문자(+, -, *, /, ^, %, =)를 담고 있으므로, Math.floor(Math.random() * 7)로 각 공백 자리에 들어갈 연산자 또는 등호를 무작위로 선택합니다. 연산자가 무작위로 삽입되기 때문에 실행할 때마다 결과가 달라질 수 있지만, 항상 성립하는 등식만 출력됩니다.
출력 결과
콘솔에는 다음과 같이 출력됩니다.
[ '5+3=8', '9=27/3', '5^2=25', '1=5%2', '3=3%3^30', '3^3+3=30', '3+3^3=30' ]