[프로그래머스][JAVA] 시소 짝꿍

링크

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

프로그래머스

 

 

설명

일단 이중 반복문으로 마구마구 했을 때 방법은 알았지만, 효율적으로 하는 방법이 아예 생각나지 않았다.

그래서 괜찮은 풀이들을 찾게 보게 되었고 좋은 힌트들을 발견하였다.

https://mag1c.tistory.com/295, https://yejin72.tistory.com/109

두 링크의 풀이가 나에겐 제일 와닿았다.

 

각 weight를 가벼운 순 - 무거운 순으로 정렬한다.

시소는 2, 3, 4 간격으로 둘 수 있기 때문에
이 경우 무게가 같은 것을 비교하는 경우의 수는
1:1, 1:2, 2:3, 2:4(=1:2), 3:4 비율로 몸무게가 같은 것을 확인하고 이렇게 된다.

 

가벼운 순 체크를 하면서 해당 비율의 몸무게가 없는 경우 몸무게마다 count를 추가해준다.

(다음 순번에 비율을 체크할 때 같은 비율 몸무게가 있다면 그 사람 수만큼 카운트를 추가해줄 수 있는 것이기 때문)

 

case) [100, 100, 100, 200, 300]

 

ex. 1) 100, map = {};

100일 때 비어있기 때문에 100에 추가할 사람 없음.

map에 {100 : 1} 추가

 

ex. 2) 100, map = {{100: 1}}

다음 100은 존재하기 때문에 시소 짝은 1쌍 나옴.

answer 에 1 추가, map에 {100: 2} 로 변경

 

ex. 3) 100, map = {{100: 2}}

다음 100은 존재하기 때문에 시소 짝은 2쌍 나옴

answer에 2 추가, map에 {100: 3} 로 변경

 

ex. 4) 200, map = {{100: 3}}

다음 200은 비어있기 때문에 200에 추가할 사람 없음.

100, 200인 경우 시소 짝이 됨 (1:2 비율)

answer에 3 추가, map에 {100: 3}, {200: 1} 추가

 

와 같은 형태로 진행되는 형태

 

 

풀이

실패 코드

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        int len = weights.length;
        for (int i=0; i<len; i++) {
            for (int j=i+1; j<len; j++) {
                
                int weightA = weights[i];
                int weightB = weights[j];
                boolean balanced = findBalanceSiso(weightA, weightB);
                // System.out.println(weightA + " " + weightB + " " + balanced);
                if (balanced) answer++;
            }
        }
        return answer;
    }
    
    private boolean findBalanceSiso(int weightA, int weightB) {
        for (int i=2; i<=4; i++) {
            int AWeight = weightA * i;
            for(int j=2; j<=4; j++) {
                int BWeight = weightB * j;
                if (AWeight == BWeight) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

성공 코드

import java.util.*;

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        // a -> b 정렬 
        Arrays.sort(weights);
        int len = weights.length;
        // 정렬 후 체크 시 1배, 2/3배, 1/2배, 3/4배 가 존재한다면 시소의 균형을 맞출 수 있음
        Map<Double, Integer> map = new HashMap<>();
        for (int i=0; i<len; i++) {
            double caseOrigin = weights[i]*1.0;
    		double case1 = caseOrigin;
    		double case2 = (weights[i]*2.0)/3.0;
    		double case3 = (weights[i]*1.0)/2.0;
    		double case4 = (weights[i]*3.0)/4.0;
            
            if(map.containsKey(case1)) {
                answer += map.get(case1);
            }
            
            if(map.containsKey(case2)) {
                answer += map.get(case2);
            }
            
            if(map.containsKey(case3)) {
                answer += map.get(case3);
            }
            
            if(map.containsKey(case4)) {
                answer += map.get(case4);
            }
            
            // 다 존재하지 않는다면 일단 caseOrigin 꺼 추가
            map.put(caseOrigin, map.getOrDefault(caseOrigin, 0) + 1);
        }
        
        return answer;
    }
    
    private boolean findBalanceSiso(int weightA, int weightB) {
        for (int i=2; i<=4; i++) {
            int AWeight = weightA * i;
            for(int j=2; j<=4; j++) {
                int BWeight = weightB * j;
                if (AWeight == BWeight) {
                    return true;
                }
            }
        }
        
        return false;
    }
}