[프로그래머스] javascript | Level1 삼총사 (⭐️백트래킹으로 풀어보기)

문제

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.

한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.

 

제한사항

• 3 ≤ number의 길이 ≤ 13
• -1,000 ≤ number의 각 원소 ≤ 1,000
• 서로 다른 학생의 정수 번호가 같을 수 있습니다.

 

입출력

number                               result

[-2, 3, 0, 2, -5]	2
[-3, -2, -1, 0, 1, 2, 3]	5
[-1, 1, -1, 1]	0

 

for문으로 풀기

let sum = 0;
for(let i = 0; i < number.length; i++){
    for(let j = i+1; j < number.length; j++){
        for(let k = j+1; k < number.length; k++){
            if(number[i]+number[j]+number[k] === 0) sum += 1;
        }
    }
}
return sum

사실 첨에 이걸 어떻게 풀어야하나..for문으로 풀어야하나;;...
생각하다가..못풀고 다른답안 참고함.
3개의 조합을 찾아야되니 for문을 세번 돌려야함.
그런데 조합의 개수가 많아질경우 for문으로 계속 반복해서 돌리는것은 좋은 방법이 아니다. 중첩이 많아진다. 이런 조합 관련된 문제는 백트래킹으로 푸는것이 좋은 방법이라하여 백트래킹 강의를 듣고 다시 풀어봄.

 

백트래킹으로 풀기

function solution(number) {
    let answer = 0
    const G = 0;

    function backtracking(number,G,cur,ans){
        if(ans.length === 3){
            const result = ans.reduce((acc,curr) => acc+curr, 0);
            if(result === 0) {
                answer++
                return
            }
        }

        for(let i = cur; i < number.length; i++){
            ans.push(number[i]);

            backtracking(number,G,i+1,ans)
            ans.pop()
        }
    }
    
    backtracking(number,G,0,[])
    
    return answer
}

1. answer 변수에 조합 개수를 누적하기 위해 0을 할당. G는 0의 조합을 찾는 거기에 G변수에 0을 할당해주었다.

2. 백트래킹 함수에 number배열과 G변수를 파라미터값으로 넘겨주었다. 0은 i 값이다 왜냐하면 재귀를 돌면서 number 배열에 2,3,0,2,-5 이렇게 순차적으로 순회를 해야하기 때문에 초기값으로 0을 넘겨주었다. 그리고 조합을 할 빈 배열을 넘겨준다.

3. 3개의 조합이 0이되는걸 찾는 문제이므로 조건문으로 해당 조건에 맞으면 answer에 누적값을 체크하고 return 해주었다.

4. 조건문에 해당하지 않을때는 반복문을 돌면서 ans배열에 계속 추가해주고 backtracking함수로 해당 조건이 맞는지 계속 체크한다.

5. 백트래킹이 끝나면 다시 조건이 맞는지 체크해줘야 하기 때문에 pop을 해준다.

 

백트래킹 개념이 넘나 어려워서 강의를 듣고 다시 한번 풀어보았다..근데 삼총사가 레벨 1문제다 보니 백트래킹으로 어렵지 않게 풀었지만..난이도가 높아지면 못풀거같기도..ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ...히잉~~~~