TIL 20241019 (삼총사 - 알고리즘)

삼총사 (알고리즘)

 

코드 1

function solution(number) {
    let answer = 0;

    function backtrack(start, count, sum) {
        if (count === 3 && sum === 0) {
            answer++;
            return;
        }

        if (count > 3 || start >= number.length) {
            return;
        }

        for (var i = start; i < number.length; i++) {
            var current = number[i];
            backtrack(i + 1, count + 1, sum + current);
        }
    }

    backtrack(0, 0, 0);

    return answer;
}

 

코드1 설명

코드1은 재귀적 백트래킹 방법으로 삼총사를 만들수 있는 방법을 찾았다.

function solution(number) {

solution 함수를 만들고 매개변수로 number 배열을 받는다.

 

    let answer = 0;

삼총사를 만들 수 있는 방법의 수를 받기 위한 변수를 answer로 초기화한다.

 

function backtrack(start, count, sum) {

backtrack 함수를 만들고 start(인덱스, count(선택한 숫자의 개수), sum(선택한 숫자의 합)를 매개변수로 받는다.

 

        if (count === 3 && sum === 0) {
            answer++;
            return;
        }

선택한 숫자의 개수가 3이고 합이 0이면 answer을 증가시키고 리턴한다.

 

        if (count > 3 || start >= number.length) {
            return;
        }

선택한 숫자의 개수가 3보다 크거나 인덱스가 배열의 길이보다 같거나 크면 함수를 종료한다.

 

        for (var i = start; i < number.length; i++) {

start부터 배열의 길이전까지 반복하는 반복문을 만든다.

 

            var current = number[i];

배열의 인덱스 숫자를 current 변수에 저장한다.

 

            backtrack(i + 1, count + 1, sum + current);

 

인덱스를(i+1)로 이동하고 선택한 숫자의 개수를 1 증가시키고 숫자의 합을 추가하여 함수를 재귀적으로 호출한다.

 

    backtrack(0, 0, 0);

함수를 0,0,0으로 초기화한다.

 

    return answer;
}

마지막으로 answer를 반환해 삼총사를 만들 수 있는 방법의 개수를 구할 수 있게 된다.

 

 

 

코드 2

function solution(number) {
    let answer = 0;
    const n = number.length;

    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (number[i] + number[j] + number[k] === 0) {
                    answer++;
                }
            }
        }
    }

    return answer;
}

 

코드2 설명

코드2는 중첩 반복문으로 삼총사를 만들수 있는 방법의 개수를 구했다.

function solution(number) {

solution 함수를 만들고 매개변수로 number 배열을 받는다.

 

    let answer = 0;

삼총사를 만들 수 있는 방법의 수를 받기 위한 변수를 answer로 초기화한다.

 

    const n = number.length;

 

number 배열의 길이를 n 변수에 저장한다.

 

    for (let i = 0; i < n - 2; i++) {

인덱스 i는 0부터 n - 2 전까지 반복하는 반복문을 만든다. (뒤에서 두 개의 숫자를 선택해야 해서)

 

        for (let j = i + 1; j < n - 1; j++) {

인덱스 j는 i + 1부터 n - 1 전까지 반복하는 반복문을 만든다. (j는 i보다 큰 값을 가져야한다)

 

            for (let k = j + 1; k < n; k++) {

인덱스 k는 j + 1부터 n 전까지 반복하는 반복문을 만든다. (k는 j보다 큰 값을 가져아한다)

 

                if (number[i] + number[j] + number[k] === 0) {

세 숫자의 합이 0인지 확인을 한다.

 

                    answer++;

합이 0이면 answer에 값을 증가시킨다.

 

                }
            }
        }
    }

세 번째, 두 번째, 첫 번째 반복문을 종료한다.

 

    return answer;
}

마지막으로 answer를 반환해 삼총사를 만들 수 있는 방법의 개수를 구할 수 있게 된다.

 

 

 

코드1과 코드2 중에서는 코드2가 더 효율적인 코드다.

코드2는 시간 복잡도가 코드1보다 더 낮고 모든 조합을 확인하기 때문이다.