프로그래머스 코딩테스트 LV. 1 - 삼총사

삼총사

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

function solution(number) {
    let answer = 0;
    const getCombinations = function (arr, selectNumber) {
        const results = [];
        // 종료조건: 반복할 게 없기 때문에 반환
        if (selectNumber === 1) return arr.map((el) => [el]);
        
        // fixed는 arr의 원소, index는 원소의 인덱스, origin은 arr 자체
        arr.forEach((fixed, index, origin) => {
            const rest = origin.slice(index + 1);
            // 종료조건까지 가기 위하여 selectNumber - 1
            const combinations = getCombinations(rest, selectNumber - 1);
            const attached = combinations.map((el) => [fixed, ...el]);
            results.push(...attached);
        });

        return results;
    }

    answer = getCombinations(number, 3)
    return  answer.filter(([a, b, c]) => a+b+c === 0).length;
}

• 스터디원분에게 도움을 받은 코드이다. 해당 풀이는 순열과 조합이라는 알고리즘을 이해하고 있어야 풀이가 훨씬 쉽다.
• 처음에 내가 생각했던 코드는 3개의 for문을 사용해서 하나의 원소의 반복이 끝나면 다음 원소로 넘어가서 세 개의 원소가 0이 될 때까지의 조건으로 반복문을 실행하는 방식을 생각했다.

예시

function solution(number) {
    var answer = 0;
    for(let i =0; i < number.length-2; i++){
        for(let j = i+1; j < number.length-1; j++){
            for(let k = j+1; k < number.length; k++){
                  const sum = number[i] + number[j] + number[k]
                if(sum === 0) answer++
            }
        }
    }
    return answer;
}

• 이런 식으로도 풀이가 가능하기는 하지만 시간복잡도에 의해서 효율성이 떨어지기 때문에 알고리즘에 대해 이하고 있다면 순열과 조합에 대해 이해하여 풀이하는게 좋다.

 

출처 및 참고자료

1. 프로그래머스 코딩테스트 다른 사람의 풀이, https://school.programmers.co.kr/learn/courses/30/lessons/131705/solution_groups?language=javascript 

프로그래머스

2. [알고리즘 JS] - 순열과 조합 구현 (자바스크립트), https://velog.io/@rlatp1409/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-JS-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EA%B5%AC%ED%98%84-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8