20230618 TIL

프로그래머스 1단계 삼총사

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

나의 풀이

for 구문을 3중으로 중첩해서 배열을 골라내서 더한 값이 0일 때 answer에 1씩 더하는 방식으로 코드를 작성했다. 하지만 이렇게 하면 시간복잡도가 높아질 것 같다. 그리고 지금은 삼총사라서 반복문을 3번만 중첩하는 것이지만 숫자가 더 커지면 중첩되는 반복문이 더 많아진다. 이경우 찾아보니까 재귀함수를 써서 작성하는 것이 좋다고 한다.

function solution(number) {
    let answer = 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)
                    answer += 1;
        }
    }
    return answer;
}

다른사람 풀이

function solution(number) {
    let result = 0;

    const combination = (current, start) => {
        if (current.length === 3) {
            result += current.reduce((acc, cur) => acc + cur, 0) === 0 ? 1 : 0;
            return;
        }

        for (let i = start; i < number.length; i++) {
            combination([...current, number[i]], i + 1);
        }
    }
    combination([], 0);
    return result;
}

알게된 것

재귀함수

아래처럼 함수 내부에서 자기자신의 함수를 다시 호출하는 구조로 만들어진 함수를 재귀함수라고 한다. 입력되는 파라미터가 1보다 작은 수일 경우 1을 return 하면서 종료한다. 재귀함수는 함수내부에서 자신을 다시 호출하기 때문에 계속 반복된다. 그렇기 때문에 종료 조건을 꼭 만들어주어야 한다.

function factorial(num) {
	if (num < 1) {
    	return 1;
    }
    return num * factorial(num - 1);
}

재귀함수를 사용하면 코드가 짧아지고 코드 유지보수에도 이점이 있으며 가독성이 높아진다. 하지만 메모리를 많이 차지하기 때문에 호출하는 횟수가 많아지면 스택오버플로우가 발생할 수 있다고 한다. 상황에 맞게 잘 사용해야 한다.