15654

문제풀이

자연수 N개와 M개가 주어졌을 때 N개의 자연수 중에서 M개를 고른 수열을 모두 구해서 출력 (n개의 자연수는 모두 다른 수이다)

입력

• n, m: 자연수
• arr: n 개의 수

로직

1,2와 2,1이 다른 수열로 취급되는 순서가 중요하지 않은 조합문제다.

조합을 구하는 함수 로직

1. 조합된 부분 집합을 담을 results 변수를 선언한다.
2. depth가 0인 재귀함수를 호출한다.
   1. depth가 r까지 도달하면 상위 스코프에 선언된 results 변수에 tmp 배열을 r까지 복사해서 담고 반환한다.
   2. i를 depth부터 n까지 반복한다.
   3. 원소의 순서를 변경한다.(i <-> depth) 이로써 앞에서부터 r까지만 고르면 모든 경우의 수를 충족 시킬 수 있다.
   4. 원소의 순서가 변경된 배열과 depth를 1 증가시켜서 재귀함수를 호출한다.
   5. 원소의 순서를 원래대로 변경한다. (i <-> depth)
3. results 변수를 반환한다.

조합 함수로 수열을 구했으면 문제에서 요구하는 대로 사전 순으로 정렬해서 출력한다.

맞왜틀

• 첫 번째 방법은 slice로 매번 배열을 복사해서 results 변수에 선택한 원소를 담기 때문에 속도가 더 걸린다.
• 첫 번째 방법은 배열의 순서를 변경해서 원소를 선택하기 때문에 입력 받았을 때 정렬을 해도 최종 결과가 원하는 순서대로 출력되지 않는다. 따라서 부분집함을 다 구한다음에 정렬하기 때문에 시간이 더 걸린다.

리팩토링

solution2

• 1 1, 7 7과 같이 중복되지 않도록 isSelected를 배열을 만들어서 체크한다.
• 선택을 할 때 순서를 변경하지 않고 원소를 임시 배열에 추가한다.
• 입력을 받았을 때 정렬해도 최종 결과에서 원하는 순서대로 출력된다.

solution3

• results 변수를 재귀함수내에서 선언한다.
• depth === r 일때 반환하는 값을 rsults 변수에 담는다.
• 재귀함수는 results를 반환한다.
• combination은 recursive(m, 0)를 바로 반환한다.

solution4

• solution 함수를 제거하고 코드를 간결화 한다.