[알고리즘/인프런] 중복 순열

문제

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

 

풀이

function solution(n, m) {
  let answer = [];
  let picked = Array.from({ length: m }, () => 0);

  function DFS(L) {
    if (L === m) {
      let copy = [...picked];
      answer = [...answer, copy];
    } else {
      for (let i = 1; i <= n; i++) {
        picked[L] = i;
        DFS(L + 1);
      }
    }
  }

  DFS(0);
  return answer;
}

answer에 새로운 순열을 추가할 때 배열을 복사하지 않으면 상위 변수 picked를 참조해 값이 유지되지 않는다. 이는 배열을 추가했을 때 동일한 주소를 바라보고 있기 때문이다. 즉, 아래와 같이 해당 주소의 배열 값을 변경할 때 그 주소를 참조하고 있는 모든 배열이 변경되는 예상치 못한 문제가 발생할 수 있다.

 

  function DFS(L) {
    if (L === m) {
      console.log("tmp: ", picked);
      answer = [...answer, picked];
    } else {
      for (let i = 1; i <= n; i++) {
        picked[L] = i;
        DFS(L + 1);
      }
    }
  }

// 결과 
tmp:  [ 1, 1 ]
tmp:  [ 1, 2 ]
tmp:  [ 1, 3 ]
tmp:  [ 2, 1 ]
tmp:  [ 2, 2 ]
tmp:  [ 2, 3 ]
tmp:  [ 3, 1 ]
tmp:  [ 3, 2 ]
tmp:  [ 3, 3 ]
[
  [ 3, 3 ], [ 3, 3 ],
  [ 3, 3 ], [ 3, 3 ],
  [ 3, 3 ], [ 3, 3 ],
  [ 3, 3 ], [ 3, 3 ],
  [ 3, 3 ]
]

이 문제를 해결하기 위해 해당 배열을 복사해 새로운 주소에 값을 저장해야 한다.

if (L === m) {
      let copy = [...picked];
      answer = [...answer, copy];
    }