프로그래머스_Java_시소짝꿍

문제

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

프로그래머스

풀이

위 문제에서 짝을 지을 수 있는 경우의 수를 아래처럼 표현할 수 있다. 아래에서 나올 수 있는 두수의 관계는 (1, 2/3, 2, 4/3)으로 4가지이다.

	2배	3배	4배
1/2배	2/2	3/2	4/2
1/3배	2/3	3/3	4/3
1/4배	2/4	3/4	4/4

[100, 200]이 무게 정보로 주어졌을 때, 100의 2배는 200이고, 200의 1/2배는 100이다. 따라서, 중복으로 체크되는 것을 막기 위해서 위 표에서 1보다 큰 값들만 사용한다.

• 같은 무게의 사람이 여러명일 때

[10, 10, 10, 10, 10] 처럼 무게정보가 주어졌을 때, 5개중에 2개를 선택하는 방법은 5*4/2 처럼 계산할 수 있다.

long n = 같은 무게의 사람 수;
if (n>1) answer += (n-1)*n/2;

• 다른 무게의 사람들을 확인

[100, 100, 100, 100, 200, 200] 처럼 무게정보가 주어졌다고 해보자.

이때 4개의 100중에 1개 2개의 200 중에 1개를 선택하는 방법은 4*2처럼 계산할 수 있다.

long n = 같은 무게의 사람 수;
answer += n * (다른 무게의 사람수);

코드

import java.util.*;

class Solution {
    public long solution(int[] weights) {
        // counter
        Map<Integer, Long> counter = new HashMap();
        for (int w : weights){
            counter.put(w, counter.getOrDefault(w, 0L)+1);
        }
        
        // match
        long answer = 0;
        for (int w : counter.keySet()){
            // 같은 무게의 사람이 여러 명일 때
            long n = counter.getOrDefault(w, 0L);
            if (n>1) answer += (n-1)*n/2;
            
            // 다른 무게의 사람
            if (w%2==0) answer += n*counter.getOrDefault(w*3/2, 0L);
            if (w%3==0) answer += n*counter.getOrDefault(w*4/3, 0L);
            answer += n*counter.getOrDefault(w*2, 0L);
        }
        return answer;
    }
}