최근, 예전에 못 풀었던 코딩테스트 문제들을 다시 보고있다.
최대한 풀려고 노력은 해 보지만 특별한 알고리즘을 써야하는 문제에선 그냥 꽉 막혀버리는 경향이 있다.
그래서 정확히 이해하고 반쯤 외우고자(?) 한번 정리해본다.
1. 순열 (nCr)
고등학교 수학시간에 배웠던 공식이다.
만약 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개면 그냥 종료 시키는건데, 항상 우리는 value로 1씩 숫자를 빼놓을 예정이므로, 조건문은 0이 아닌 1에서 종료된다
- 현재 숫자부터 조합을 돌릴 value 하나와, 그 뒷 숫자들을 restArr라는 배열로 잘라준다
- 그리고 restArr와 뽑을 갯수를 -1 하여 현재 함수를 재귀실행 시켜준다. + (여기서 number가 1이 될 때 까지 계속 재귀실행 될 것이다)
- 그렇게 뽑은 모든 재귀 함수들을 현재 value와 하나의 배열로 합쳐준다.
- 그 배열을 result에 넣고
- 리턴하면 끝
- +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]] 로,
앞서 직접 값을 구했을 때와 동일한 값을 얻을 수 있다.
예전에 문제를 풀 때 보다 순열을 구하는 부분에 초점을 맞춰 하나씩 코드를 따라가다보니, 좀 더 쉽게 이해가 된 느낌이다.
설명으로 적었을 땐 개판이기 그지없지만, 이렇게라도 나에게, 또 누군가에게 도움이 된다면 참 좋겠다.
그래도 미래의 내가 또 보러오진 않았으면 좋겠다...ㅎ