JS/알고리즘(코테)

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

주디_JUDI 2023. 7. 1. 16:39

삼총사

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