2Level / 연습 문제 / 시소 짝꿍

문제 설명

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

프로그래머스

 

문제 풀이 방법

이 문제에서 제한 사항을 보게 되면 주어지는 weights의 갯수는 100,000개이다.즉, 이중 for문을 이용하게 되면 100억 번의 시간 복잡도를 갖게되므로 시간초과 오류가 발생할 수 있다.(나는 실제로 이중 for문으로 푸러봤다가 실패했다...)

 

그렇다면 weights를 순회할 for문은 한개로 제한된 상황에서 어떻게 각 요소를 비교할까?

 

이는 객체를 이용해 각 요소의 key와 value를 이용해 풀 수 있었다.객체의 key는 비교해야할 무게, value에는 그 무게의 갯수를 저장한다.

 

이후 반복문에서 비교 케이스와 비교를 하는데, 비교 케이스는 weights를 오름차순으로 정렬하여 1, 3/2, 2, 4/3 총 4가지를 비교했다.(오름 차순으로 정렬했기에 0.5 같은 배율을 생각안해도 된다.)

 

비교를 하는 조건문에서 객체[비교하는 무게] 에 해당하는 value를 answer에 더해준다.(1:1 배율에서는 비교하는 자신을 갯수에서 빼야한다)

 

4가지 비교를 마친뒤 자기 자신은 오름 차순으로 정렬된 배열에서 비교를 했으니 객체에서 갯수를 한개 빼준다.

 

 

참고한 코드

const solution = (weights) => {
    let dic = {};
    let answer = 0;
    
    weights.sort((a, b) => a - b);
    weights.forEach(e => {
        if(dic[e] === undefined) dic[e] = 1;
        else dic[e] += 1;
    });
    
    weights.forEach(e => {
        if(dic[e] > 1) answer += (dic[e] - 1);
        if(dic[e * (3 / 2)] > 0) answer += (dic[e * (3 / 2)]);
        if(dic[e * 2] > 0) answer += (dic[e * 2]);
        if(dic[e * (4 / 3)] > 0) answer += (dic[e * (4 / 3)]);
        
        dic[e] -= 1;
    })
    
    return answer;
}