[Java Script] 조합 구하기 (+ 상세한 해설)

최근, 예전에 못 풀었던 코딩테스트 문제들을 다시 보고있다.

최대한 풀려고 노력은 해 보지만 특별한 알고리즘을 써야하는 문제에선 그냥 꽉 막혀버리는 경향이 있다.

그래서 정확히 이해하고 반쯤 외우고자(?) 한번 정리해본다.

 

1. 순열 (n​Cr)

고등학교​​ 수학시간에 배웠던 공식이다.

만약 4개 중 3개를 뽑는 상황이라면

(4!) / (3!) = (4*3*2*1) / (3*2*1) = 4 -> 4가지 경우의 수를 지닌다.

로 정리할 수 있다.

const arr = [1, 2, 3, 4]
const answer = [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

​검증을 위해 펜에 직접 적어가면서 경우의 수를 따져봐도 결과는 동일하게 4개의 결과가 나온다.

그럼 이걸 코드로 구현하면 어떻게 될까?

---

2. 순열 코드구현

const getCombination = (arr, number) => {
    const result = [];
    if (number === 1) return arr.map(v => [v]) // 1
    
    arr.forEach((value, index, array) => {
        if (array.length < number) return // +a
        
        const restArr = array.slice(index + 1) // 2
        
        const restCombi = getCombination(restArr, number-1) // 3
        const target = restCombi.map(rest => [value, ...rest]) // 4
        
        result.push(...target) // 5
    })
    return result // 6 끝
}

우선 완성된 코드는 이렇게 생겼다.

재귀함수를 통해 구현된 코드이며, 주석처리한 한 줄씩 설명을 적겠다.

 

1.  이 함수의 종료 조건문이다. 뽑을 숫자가 1개면 그냥 종료 시키는건데, 항상 우리는 value로 1씩 숫자를 빼놓을 예정이므로, 조건문은 0이 아닌 1에서 종료된다
2. 현재 숫자부터 조합을 돌릴 value 하나와, 그 뒷 숫자들을 restArr라는 배열로 잘라준다
3. 그리고 restArr와 뽑을 갯수를 -1 하여 현재 함수를 재귀실행 시켜준다. + (여기서 number가 1이 될 때 까지 계속 재귀실행 될 것이다)
4. 그렇게 뽑은 모든 재귀 함수들을 현재 value와 하나의 배열로 합쳐준다.
5. 그 배열을 result에 넣고
6. 리턴하면 끝
7. +a는 뽑아야 할 갯수가 남은 배열보다 짧을 때 종료하는 성능 개선을 위한 조건문이다.

위 설명으로도 본인은 많이 헷갈렸기에, 배열 [1, 2, 3, 4]에서 3개를 뽑는 조합을 이용해서 어떻게 실행되는지 상세히 적어 본다면

---

3. 코드 한줄씩 생각해보기

 

1. 함수 시작, value(고정값)가 1일 때

arr = [1, 2, 3, 4] number = 3

value = 1 (첫번째 문자)

restArr = [2, 3, 4]

이후 재귀 실행한다.

 

  1-1. 1차 재귀

  arr =[2, 3, 4] / number = 2

  value = 2 (첫번째 문자)

  restArr [3, 4]

  한번 더 재귀실행한다.

  

  1-2. 2차 재귀

  arr = [3, 4] number = 1

  엇, 여기선 number가 1이다.
  그럼 조건대로 map 함수를 돌려 [[3], [4]] 를 반환한다.

 

  1-3. 2차재귀 결과로 1차 재귀 마저 실행

  재귀실행 조건이 끝났다면 결과를 만들어주면 된다.

  1차 재귀 때 value가 2 였으므로, map 함수를 이용해 이와 합쳐준다

  결국 result = [[2, 3], [2, 4]] 를 return 한다.

 

  1-4. 1차재귀 결과로 초기 마저 실행

  여기서도 앞서 value를 1을 뽑아 놓은것과 합쳐주면 끝이다.

  결국, [[1, 2, 3], [1, 3, 4]] 두 배열을 result에 push 해주고 다음을 준비하자.

 

2. forEach 두번째 시작, value가 2일때

arr = [1, 2, 3, 4] number = 3

restArr = [3, 4] (2 이후 부터 뽑았으니까)

이후 재귀실행 한다.

 

  2-1. 1차 재귀

  arr = [3, 4] number = 2

  value = 3, 

  restArr = [4]

  결과를 알 것 같지만, 한 번 더 재귀해보자.

 

  2-2. 2차 재귀

  arr=[4] number = 1

  역시 number가 1이므로 바로 [[4]] 를 반환하고

 

  2-3 1차재귀 마저 실행

  앞선 고정값 3과 합쳐서 값을 리턴해주면 [[3,4]] 가 된다.

 

  2-4, 시작 마저실행

  여기에 고정값 2와 합쳐주면 [[2,3,4]]가 완성이된다.
  이를 result에 push 해 주면 [[1, 2, 3], [1, 3, 4], [2,3,4]] 

 

3. forEach 세 번째 시작, value가 3일 때

엇, 여긴 실행하자마자 아까 조건문에 의해 array 길이가 2밖에 되지 않아, 반복문이 종료된다.
value가 4일 때도 마찬가지다.

 

4. 결국 해당 함수를 통해 얻은 값은 [[1, 2, 3], [1, 3, 4], [2,3,4]] 로,

앞서 직접 값을 구했을 때와 동일한 값을 얻을 수 있다.

 

---

예전에 문제를 풀 때 보다 순열을 구하는 부분에 초점을 맞춰 하나씩 코드를 따라가다보니, 좀 더 쉽게 이해가 된 느낌이다.

설명으로 적었을 땐 개판이기 그지없지만, 이렇게라도 나에게, 또 누군가에게 도움이 된다면 참 좋겠다.

 

그래도 미래의 내가 또 보러오진 않았으면 좋겠다...ㅎ