자바스크립트에서 n개의 문자 배열로 반복 문자 없는 모든 조합 문자열 만들기

문제 이해하기

각각 한 글자짜리 문자들을 담고 있는 n개의 별개 배열이 있다고 가정해 봅시다. 우리는 이 모든 배열을 인수로 받아 처리하는 자바스크립트 함수를 작성해야 합니다.

이 함수는 다음 두 가지 조건을 만족하는 모든 가능한 문자열 조합을 생성해야 합니다.

각 배열에서 정확히 하나의 문자를 가져와야 합니다.
생성된 문자열에는 반복되는 문자가 없어야 합니다. (배열끼리 서로 같은 요소를 포함할 수 있기 때문입니다.)

이번 예제에서는 편의상 세 개의 배열을 사용하지만, 작성하는 함수는 배열의 개수와 관계없이 유연하게 동작하도록 만들 것입니다.

const arr1 = ['a', 'b', 'c', 'd'];
const arr2 = ['e', 'f', 'g', 'a'];
const arr3 = ['m', 'n', 'o', 'g', 'k'];

예제 코드

위 문제를 해결하는 전체 코드는 다음과 같습니다.

const arr1 = ['a','b','c','d'];
const arr2 = ['e','f','g','a'];
const arr3 = ['m', 'n', 'o', 'g', 'k'];

const allCombinations = (...arrs) => {
   let res = [];
   const reduced = arrs.reduce((acc, b) => acc.reduce((r, v) => {
      return r.concat(b.map(el => {
         return [].concat(v, el);
      }))
   }, [])
   );
   res = reduced.filter(el => new Set(el).size === el.length);
   return res.map(el => el.join(' '));
};
console.log(allCombinations(arr1, arr2, arr3));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[
   'a e m', 'a e n', 'a e o', 'a e g', 'a e k',
   'a f m', 'a f n', 'a f o', 'a f g', 'a f k',
   'a g m', 'a g n', 'a g o', 'a g k', 'b e m',
   'b e n', 'b e o', 'b e g', 'b e k', 'b f m',
   'b f n', 'b f o', 'b f g', 'b f k', 'b g m',
   'b g n', 'b g o', 'b g k', 'b a m', 'b a n',
   'b a o', 'b a g', 'b a k', 'c e m', 'c e n',
   'c e o', 'c e g', 'c e k', 'c f m', 'c f n',
   'c f o', 'c f g', 'c f k', 'c g m', 'c g n',
   'c g o', 'c g k', 'c a m', 'c a n', 'c a o',
   'c a g', 'c a k', 'd e m', 'd e n', 'd e o',
   'd e g', 'd e k', 'd f m', 'd f n', 'd f o',
   'd f g', 'd f k', 'd g m', 'd g n', 'd g o',
   'd g k', 'd a m', 'd a n', 'd a o', 'd a g',
   'd a k'
]

코드 동작 원리

이 코드의 핵심 로직은 크게 세 단계로 나눌 수 있습니다.

데카르트 곱(Cartesian Product) 생성: reduce()를 중첩하여 사용함으로써, 첫 번째 배열부터 시작해 이전까지 누적된 조합 배열(acc)과 새로운 배열(b)의 모든 요소를 짝지어 새로운 조합을 만들어냅니다. 이 과정에서 나머지 매개변수(...arrs)를 활용했기 때문에 배열이 몇 개가 들어오더라도 동일하게 처리됩니다.
중복 제거: filter()와 함께 new Set(el).size === el.length 조건을 사용합니다. Set은 중복된 값을 저장하지 않으므로, 배열을 Set으로 변환했을 때 그 크기가 원래 배열의 길이와 같다면 해당 조합에는 반복 문자가 없다는 의미입니다.
문자열 변환: 마지막으로 map()과 join(' ')을 통해 문자 배열을 공백으로 구분된 완성된 문자열 형태로 변환하여 반환합니다.

이처럼 reduce, Set, filter를 조합하면 별도의 재귀 함수나 복잡한 반복문 없이도 간결하고 선언적인 방식으로 문제를 해결할 수 있습니다.