시소짝궁

문제 설명

무게 별 시소의 특정지점에 있을 때 평행을 유지할 수 있다.

짝궁을 이룰 수 있는 경우의 수를 구하시오.

시소는 중심으로 부터 2,3,4m 거리 지점에 좌석이 있고 해당 사람 무게 * 지점 == 다른 사람 무게 * 지점 이 같은 경우라면 짝궁을 이룰 수 있다.

생각한 아이디어

• 이분탐색 → x
• 최대공약수 → 어차피 n^2

풀이 [자료구조를 이용한 풀이]

맵 2개를 이용해 풀이함.

1. 하나의 map은 [무게, 사람 수]로 구성
2. 또 다른 map은 [2,3,4m 지점의 무게, 원천지] 로 구성

1번에서 중복으로 같은 무게를 가지고 있는 경우 pair를 자기들끼리 이룰 수 있으므로 계산해줌

2번에서는 원천지로 부터 2개 이상을 가지고 있으면 pair를 이룰 수 있으므로 계산 해줌

import java.util.*;
import java.util.stream.*;

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        Map<Integer, Integer> maps=new HashMap<>();
        Arrays.stream(weights)
            .forEach(key->maps.put(key,maps.getOrDefault(key,0)+1));
        
        
        Map<Integer, List<Integer>> sources=new HashMap<>();
        
        for(Integer source : maps.keySet()){

            if(maps.get(source)>=2){
                int n=maps.get(source);
                n--;
                answer+=((long)n * (n+1) / 2); // 10만 10만은 100억 이므로 overfow
            }
            for(int i=2; i<=4; i++){
                int nKey=source*i;
                
                if(sources.containsKey(nKey)){
                    sources.get(nKey).add(source);
                }else{
                    List<Integer> sourceList=new ArrayList<>();
                    sourceList.add(source);
                    sources.put(nKey,sourceList);
                }
            }
        }

        for(Integer val: sources.keySet()){
            List<Integer> list=sources.get(val);
            if(list.size()==1) continue;
           
            for(int i=0; i<list.size(); i++){
                int left=list.get(i);
                for(int j=i+1; j<list.size(); j++){
                    int right=list.get(j);
                    
                    answer+=((long)maps.get(left)*maps.get(right)); //5만 5만인 경우 25억으로 overflow
                }
            }
        }
                
        return answer;
    }
}