문제 이해하기
양의 정수로 이루어진 배열을 입력받아, 다음 연산을 필요한 만큼 반복 적용한 뒤 더 이상 변환이 불가능한 시점의 배열 요소 합계를 반환하는 JavaScript 함수를 작성해야 합니다.
if arr[i] > arr[j] then arr[i] = arr[i] - arr[j]
즉, 배열 안에 서로 다른 두 요소가 존재하는 한, 큰 값에서 작은 값을 빼는 연산을 계속 수행할 수 있습니다. 모든 요소가 같아지면 더 이상 변환할 수 없으며, 그때의 합계가 정답이 됩니다.
예제 코드
재귀 호출을 활용한 풀이는 다음과 같습니다.
const arr = [6, 9, 21];
const smallestSum = (arr = []) => {
const equalNums = arr => arr.reduce((a, b) => {
return (a === b) ? a : NaN;
});
if(equalNums(arr)){
return arr.reduce((a, b) => {
return a + b;
});
}else{
const sorted = arr.sort((a, b) => {
return a-b;
});
const last = sorted[arr.length-1] - sorted[0]
sorted.pop();
sorted.push(last);
return smallestSum(sorted);
};
};
console.log(smallestSum(arr));
출력 결과
9
동작 원리
이 문제의 핵심은 유클리드 호제법(Euclidean algorithm)과 밀접한 관련이 있습니다. 큰 수에서 작은 수를 반복해서 빼다 보면 결국 두 수의 최대공약수(GCD)에 도달하게 됩니다. 따라서 모든 요소가 같아져 더 이상 변환이 불가능한 시점에는, 배열의 모든 요소가 전체 배열의 최대공약수와 동일한 상태가 됩니다.
예를 들어 [6, 9, 21]의 최대공약수는 3이고, 배열의 길이가 3이므로 최종 합계는 3 × 3 = 9가 됩니다. 이는 위 코드의 실행 결과와 정확히 일치합니다.
더 효율적인 풀이
재귀적으로 배열을 정렬하고 변환하는 방식은 비효율적일 수 있습니다. reduce와 재귀 GCD 함수를 활용하면 한 번의 순회로 답을 구할 수 있습니다.
const smallestSum = (arr = []) => {
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
return arr.reduce((a, b) => gcd(a, b)) * arr.length;
};
console.log(smallestSum([6, 9, 21])); // 9이 방식은 배열을 매번 정렬하지 않으므로 훨씬 간결하고 성능 면에서도 유리합니다.