[JS로 코테 준비하기] 16. 삼총사 (feat. 백트래킹, 순열과 조합)

https://school.programmers.co.kr/learn/courses/30/lessons/131705

프로그래머스

 

JS 코드로 백트래킹을 정리해 보자. 

1부터 3까지 배열이 있을 때, 이 중에서 2개를 뽑는 방식을 예시로 알아볼 것이다.

const number = [1, 2, 3];
const r = 2;

 

1. 조합 

• 중복 없이 r개를 뽑는 경우 (순서 상관 X)
• 결과: [1, 2], [1, 3], [2, 3]

 

• 탐색 중인 인덱스(cur)를 인자로 설정하고, 다음 탐색에 i + 1을 넘긴다.
• 현재 값 이후의 값만 선택하도록 해 중복을 제거한다.
• 인덱스 순으로 선택하므로, 순서는 자연스럽게 정리된다.
  • [a, b]에서 a < b
  • [2, 1]과 같은 것이 선택될 경우는 존재 X

const tmp = [];

const backtrack = (cur) => {
    if(tmp.length === r){
        console.log(tmp);
        return;
    }

    for(let i = cur; i < number.length; i++){
        tmp.push(number[i]);
        backtrack(i + 1);
        tmp.pop();
    }   
}

backtrack(0);

 

 

2. 순열

• 중복 없이 r개를 뽑는 경우 (순서 상관 O)
• 결과: [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]

 

• 중복 선택이 가능하므로 현재 탐색 중인 값의 위치를 알 필요가 없다.
• 따라서 계속 인덱스 0부터 탐색하도록 한다.
• 단, 중복을 허용하지 않으므로 includes를 통해 현재 값의 중복을 체크한다.

const tmp = [];

const backtrack = () => {
    if(tmp.length === r){
        console.log(tmp);
        return;
    }

    for(let i = 0; i < number.length; i++){
        if(tmp.includes(number[i])) continue;
        tmp.push(number[i]);
        backtrack();
        tmp.pop();
    }   
}

backtrack();

 

 

3. 중복 조합

• 중복을 허용해 r개 뽑는 경우 (순서 상관 X)
• 현재 탐색하는 인덱스 cur을 인자로 넘겨 중복 체크 + 다음 backtrack에 i를 넘겨 중복 허용
• 결과: [1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]

 

• 탐색 중인 인덱스(cur)를 인자로 설정하고, 다음 탐색에 i를 넘긴다.
• 현재 값(i)을 포함해 중복 선택이 가능하도록 하는 것이다.
• 인덱스 순으로 선택하므로, 순서는 자연스럽게 정리된다.
  • [a, b]에서 a <= b
  • [2, 1]과 같은 것이 선택될 경우는 존재 X

const tmp = [];

const backtrack = (cur) => {
    if(tmp.length === r){
        console.log(tmp);
        return;
    }

    for(let i = cur; i < number.length; i++){
        tmp.push(number[i]);
        backtrack(i);
        tmp.pop();
    }   
}

backtrack(0);

 

 

4. 중복 순열 

•  중복을 허용해 r개 뽑는 경우 (순서 상관 O)
• 결과: [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]

 

• 중복 선택이 가능하므로 현재 탐색 중인 값의 위치를 알 필요가 없다.
• 따라서 계속 인덱스 0부터 탐색하도록 한다.

const tmp = [];

const backtrack = () => {
    if(tmp.length === r){
        console.log(tmp);
        return;
    }

    for(let i = 0; i < number.length; i++){
        tmp.push(number[i]);
        backtrack();
        tmp.pop();
    }   
}

backtrack();

 

 

소스 코드

• C++ 보다 간결한 느낌은 있다. 중복 체크 부분의 코드가 줄어서 그런 것 같다.
• 백트래킹 원리가 헷갈린다면, 백준의 n과 m 시리즈를 참고하자.

const NUM = 3;

function solution(number) {
    let ans = 0;
    const tmp = [];
    
    const backtrack = (cur) => {
        if(tmp.length === NUM){
            ans += tmp.reduce((a, b) => a + b) ? 0 : 1;
            return;
        }

        for(let i = cur; i < number.length; i++){
            tmp.push(number[i]);
            backtrack(i + 1);
            tmp.pop();
        }   
    }
    
    backtrack(0);
    
    return ans;
}

 

 

참고) tmp를 인자로 넘기고, push/pop을 스프레드로 한 번에 처리할 수도 있다.

• 정말 JS스럽다고 느낀 풀이이다.
• 사실 아직 한 방에 와닿지는 않지만, 직관적으로 이해될 수 있도록 자주 봐야겠다.

function solution(number) {
    let ans = 0;
    
    const backtrack = (tmp, cur) => {
        if(tmp.length === NUM){
            ans += tmp.reduce((a, b) => a + b) ? 0 : 1;
            return;
        }

        for(let i = cur; i < number.length; i++){
            backtrack([...tmp, number[i]], i + 1);
        }   
    }
    
    backtrack([], 0);
    
    return ans;
}