자바스크립트로 풀어보는 아름다운 배열(Beautiful Arrangement) 문제

아름다운 배열(Beautiful Arrangement)이란?

1부터 N까지의 정수가 주어졌을 때, 아름다운 배열(beautiful arrangement)은 이 숫자들로 구성된 배열 중에서 모든 위치 i(1 ≤ i ≤ N)에 대해 다음 조건 중 하나라도 성립하는 배열을 말합니다.

• i번째 위치에 놓인 숫자가 i로 나누어 떨어진다.

• i가 i번째 위치에 놓인 숫자로 나누어 떨어진다.

문제 설명

숫자 num을 입력받아, 만들 수 있는 아름다운 배열의 총 개수를 반환하는 자바스크립트 함수를 작성해야 합니다.

예를 들어, 함수의 입력이 다음과 같다고 가정해 보겠습니다.

const input = 2

그렇다면 출력 결과는 다음과 같아야 합니다.

const output = 2

출력 해설

num이 2일 때 가능한 아름다운 배열은 두 가지뿐입니다.

첫 번째 아름다운 배열은 [1, 2]이며, 두 번째 아름다운 배열은 [2, 1]입니다.

예시 코드

이를 구현한 코드는 다음과 같습니다.

const num = 4;
const countArrangements = (num = 1) => {
   let ans = 0
   const recur = (curr, vis) => {
      if (curr === 1){
         ans++;
      }else{
         for (let i = num; i; i--) {
            let possible = (i % curr === 0 || curr % i === 0);
            let visited = vis & 1 << i;
            if (possible && !visited){
               recur(curr-1, vis | 1 << i);
            }
         }
      }
   };
   recur(num, 0);
   return ans;
};
console.log(countArrangements(num));

코드 해설

먼저 최종 개수를 저장할 변수(ans)를 정의한 뒤, 여러 갈래의 경우의 수를 탐색하기 위한 재귀 함수를 만듭니다. 이 재귀 함수는 두 개의 인자만 필요합니다.

• curr: 현재 배치하려고 하는 위치(숫자)

• vis: 이미 사용한 숫자를 기록하는 비트마스크(bitmask)

vis 변수는 비트 연산을 활용해 각 숫자의 사용 여부를 효율적으로 추적합니다. 또한 큰 숫자부터 작은 숫자 순서로 탐색하기 때문에 조건을 만족하지 않는 경우를 조기에 걸러낼 수 있어, 불필요한 탐색을 줄이는 가지치기(pruning) 효과도 함께 얻을 수 있습니다.

출력 결과

위 코드를 실행하면 콘솔에는 다음과 같은 값이 출력됩니다.

8