[알고리즘] 순열(permutation)로 뽑은 모든 배열 구하기 (JavaScript)

문제설명

조건

- 재료가 담긴 stuffArr배열에서 0이 3개 이상인 엘리먼트는 제외

- 재료를 넣는 순서가 다르다면 다른 레시피로 취급 (조합이 아닌 순열임을 나타냄)

- 사용할 재료가 없거나 choiceNum보다 작다면 빈 배열 리턴

전달인자

- stuffArr : number 타입을 요소로 갖는 배열이며, 요소는 중복될 수 없음 (예시 : [1, 10, 1100, 1111])

- choiceNum : number 타입으로 1 이상 stuffArr.length 이하

출력 값

- stuffArr에서 choiceNum개의 요소를 선택하여 만들 수 있는 모든 배열을 리턴하기

- stuffArr에서 choiceNum개의 요소를 선택하여 배열을 만들고, 그것을 엘리먼트로 삼는 2차원 배열을 리턴

- 조합 및 요소는 작은 숫자에서 큰 숫자로 정렬

- 예시 : newChickenRecipe([1, 10, 1100, 1111], 2);

            [ [1, 10], [1, 1100], [1, 1111], [10, 1], [10, 1100], [10, 1111], [1111, 1], [1111, 10], [1111, 1100] ] 

 

코드 작성 포인트

- 순열 내장함수(permutation)을 만들고 재귀를 사용해서, 빈 배열 result에 엘리먼트를 담기

- 함수의 전달인자 : 재료를 담은 배열(arr), 순열로 뽑은 엘리먼트를 담는 배열(bucket), 뽑는 개수(n)

- 재귀함수 사용 시 arr에서 한 요소를 뽑아서 bucket에 담고, n에서 1을 빼주기

- 재귀함수 사용 시 arr에서 bucket에 넣은 엘리먼트는 제거해주기 (중복순열에서는 이 과정이 불필요)

- 재귀의 탈출 조건은 count가 0이 되는 경우이며, 이때 bucket을 result에 넣어주기

 

코드 작성하기

function newChickenRecipe(stuffArr, choiceNum) {
  
  // stuffArr에서 0이 3개 이상이라면 전부 필터로 거른 freshArr 배열 만들기
  let freshArr = [];

  for (let i = 0; i < stuffArr.length; i++) {
    const element = String(stuffArr[i])
      .split('')
      .filter((e) => e === '0');
    if (element.length <= 2) {
      freshArr.push(stuffArr[i]);
    }
  }

  // freshArr을 오름차순으로 정렬
  freshArr.sort((a, b) => a - b);

  // 엣지 케이스 처리
  if (freshArr.length === 0 || freshArr.length < choiceNum) return [];

  // 각 경우들을 배열 엘리먼트로 담을 빈 배열 result 선언
  let result = [];

  // freshArr를 대상으로 순열 내장함수 만들기
  const permutation = (arr, bucket, n) => {
    if (n === 0) {        // 탈출조건
      result.push(bucket);
      return;
    }

    for (let i = 0; i < arr.length; i++) {
      const choice = arr[i];         // bucket에 담을 arr의 엘리먼트
      const sliceArr = arr.slice();  // immutable하게 배열 복사
      sliceArr.splice(i, 1);         // arr에서 bucket에 담을 요소로 뺀 배열
     
      permutation(sliceArr, bucket.concat(choice), n - 1);    // 재귀
    }
  };

  // 함수 실행
  permutation(freshArr, [], choiceNum);
  
  return result;
}