숫자 n을 입력받아, 1부터 n까지의 정수를 각각 한 번씩 사용하면서 인접한 두 수의 합이 항상 완전제곱수가 되도록 배치한 배열을 반환하는 JavaScript 함수를 작성해야 합니다. 만약 조건을 만족하는 배치가 존재하지 않는다면 false를 반환합니다.
문제 이해하기
예를 들어 n이 15라면, 함수는 1부터 15까지의 모든 정수를 정확히 한 번씩 포함하는 배열을 만들어야 하며, 배열에서 나란히 있는 두 수의 합은 반드시 4, 9, 16, 25처럼 어떤 정수의 제곱이어야 합니다.
접근 방식: 백트래킹
이 문제는 백트래킹(backtracking) 기법으로 깔끔하게 해결할 수 있습니다. 동작 원리는 다음과 같습니다.
- 사용 여부 추적: 이미 사용한 숫자는 Set에 기록해 두었다가 다시 선택하지 않습니다.
- 완전제곱수 검증: 배열이 비어 있지 않다면, 새로 추가하려는 숫자 i와 현재 맨 앞 숫자의 합이 Math.sqrt(합) % 1 === 0을 만족하는지 확인합니다. 이 식이 참이면 그 합은 완전제곱수입니다.
- 선택과 되돌리기: 조건을 통과하면 숫자를 배열 앞에 추가(unshift)한 뒤 재귀 호출을 이어가고, 탐색이 실패하면 해당 숫자를 제거(shift, delete)하여 다른 후보를 시도합니다.
- 종료 조건: Set의 크기가 n에 도달하면 1부터 n까지 모든 숫자를 사용한 것이므로 탐색에 성공한 것입니다.
참고로 이 구현은 unshift로 배열의 앞쪽부터 값을 채우지만, '두 인접 수의 합'이라는 조건은 대칭적이므로 결과에는 전혀 문제가 없습니다.
예제 코드
const n = 15;
const buildSquaresArray = (n = 1, res = []) => {
const helper = (res, set, n) => {
if(set.size === n){
return true;
};
for(let i = 1; i <= n; i++){
if (set.has(i)){
continue;
};
if(res.length && Math.sqrt(res[0] + i) % 1 !== 0){
continue;
};
set.add(i);
res.unshift(i);
if(helper(res,set,n)){
return true;
}
res.shift();
set.delete(i);
};
return false;
};
return helper(res,new Set(),n) ? res : false;
};
console.log(buildSquaresArray(n));
출력 결과
n이 15일 때 콘솔에 출력되는 결과는 다음과 같습니다.
[ 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 ]
결과 검증
출력된 배열의 인접한 두 수의 합을 직접 확인해 보면 모두 완전제곱수임을 알 수 있습니다. 예를 들어 9 + 7 = 16(4²), 7 + 2 = 9(3²), 14 + 11 = 25(5²), 10 + 15 = 25(5²)이며, 나머지 인접 쌍 역시 모두 9, 16, 25 중 하나가 됩니다.
이처럼 백트래킹을 활용하면 조건을 만족하는 배치를 체계적으로 찾을 수 있습니다.