[4월 2일] 시소 짝꿍

문제

1. 시소 짝꿍

문제 설명

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

• 2 ≤ weights의 길이 ≤ 100,000
• 100 ≤ weights[i] ≤ 1,000

 

입출력 예

weights	result
[100,180,360,100,270]	4

 

내 풀이(실패)

const gcd = (a,b) => (b>0?gcd(b,a%b):a)
const lcm = (a,b) => (a*b/gcd(a,b))

function solution(weights) {
    var answer = 0;
    weights = weights.sort((a,b)=>a-b);
    console.log(weights)
    
    
    
    // 1. 두 숫자의 최소 공배수 구하기
//     2. 각 숫자 별 몇 배씩 곱했는지 -> 2,3,4라면 OK
    const list = [1,2,3,4]
    weights.forEach((weight1,index1)=>{
        weights.forEach((weight2,index2)=>{
            if(index1===index2) return;
            
            const l = lcm(weight1,weight2)
            if(list.includes(l/weight1) && list.includes(l/weight2)){          
                console.log(weight1,weight2,l);
                answer++
            }
        })
    })
    return answer/2;
}

O(n**2)으로 각 모든 조합을 돌렸다. 조합을 돌리면서 각각의 최소 공배수를 구해서, 최소공배수까지 각 값이 몇 배를 곱했는지 구해, 그 값들이 [1,2,3,4]배열 안에 있는 값이라면 answer++하는 식으로 했다. 그러면 중복해서 2번 씩 더해질 것이니 마지막에 /2를 해주었다.

결과는 테스트 1,2번 만 통과.

 

참고 풀이

function solution(weights) {
    let answer = 0;
    const store = {}; //key-value
    const cal = [1, 3/2, 2, 4/3]; //경우의 수 (1,1), (2,3), (2,4), (3,4)

    weights.sort((a,b)=> b - a).forEach((w) => { //내림차순 정렬 후, 전체 돌면서
        let s;
        cal.forEach((i)=>{
            if( s = w * i, store[s] ){ //해당 비율을 곱한 값이 store에 존재할 경우
              answer += store[s];
            }
        });
        if (!store[w]) store[w] = 1;
        else store[w]++;
    });
    return answer;
}

1. if(s=w*i,store[s])?이게 무슨 풀이지 => i에 w를 곱하고, 결과를 s변수에 저장 & store데이터 구조에 있는지 확인

2. cal배열에 [1,3/2,2,4/3]을 넣어주었다. 각각 둘을 1,1배씩 해주었을 경우, 2,3배씩 해주었을 경우, 2,4배, 3,4배를 해주었을 경우에 대한 숫자이다.

3. 동일한 값이 여러 개 있는 경우를 대비하여 store객체를 이용하였다. store객체에 저장이 안되었다면 store[w]=1로 저장하고, 저장되어 있다면 store[w]++한다. => cal값을 곱한 값이 같은 값이 3개일 경우, 처음에는 1을 더하지만 그 다음은 2을 더하는 식 

느낀점

최소공배수, 최대공약수를 구하는 함수에서부터 잠깐 멈칫했다. 풀이의 일부분인 이런 기본적인 알고리즘도 잊고 있었다니. 이런 기초가 아직 부족한가보다. 이런 알고리즘을 좀 정리 한 번 해야겠다.

const gcd = (a,b) => (b>0?gcd(b,a%b):a)
const lcm = (a,b) => (a*b/gcd(a,b))

아직 많이 부족함을 느꼈다 .. 참고 풀이를 보고도 바로 이해를 하지 못하고 직접 손으로 써가며 '이게 이거구나' 알게 되었다. 많이 풀어봐서 많이 익혀야지 . 그리고, 이전에 틀렸던 문제들도 다시 한 번씩 풀어봐야겠다.