프로그래머스 코딩테스트 연습 - 시소 짝꿍 JavaScript

처음에 작성한 코드는 다음과 같았다.

function solution(weights) {
    let answer = 0;
    // 2 3 4 미리 구하기
    const weightsObj = {};
    weights.forEach(el => {
        if(!weightsObj[el]) {
           weightsObj[el] = [2, 3, 4].map(item => item * el);            
        }
    })
    for(let i = 0; i < weights.length - 1; i++) {
        const now = weightsObj[weights[i]];
        for(let j = i + 1; j < weights.length; j++) {
            const weight = weights[j];
            let checker = false;
            weightsObj[weight].forEach(v => {
                if(now.includes(v) && !checker) {
                    checker = true;
                }
            });
            if(checker) {
                answer++;
            }
        }
    }
    return answer;
}

시간초과로 문제 해결에 실패하여 다른 방법에 대해서 생각하였다.

 

쉽사리 문제 해결 방법에 대해서 생각해내지 못했는데 캐싱을 사용해서 중복 계산을 줄여야 한다는 점과 경우의 수가 제한되어 있다는 등 검색을 통해서 힌트를 많이 보았다.

결국, 내 스스로 푼 문제는 아니었으므로 더 공부하고 이해할 수 있도록 해야겠다.

function solution(weights) {
    let answer = 0;
    const distance = [1, 3 / 2, 2, 4 / 3]; // 경우의 수
    const memo = {};
    
    weights.sort((a,b)=> b - a).forEach(weight => {
        for(let i of distance) {
            const now = weight * i;
            if(memo[now]) {
                answer += memo[now];
            }
        }
        if(memo[weight]) {
            memo[weight]++;
        }else {
            memo[weight] = 1;
        }
    })
    return answer;
}