[Programmers] 시소 짝궁 (Java)

문제링크

문제 설명

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

제한 사항

• 2 ≤ weights의 길이 ≤ 100,000
• 100 ≤ weights[i] ≤ 1,000
  
  • 몸무게 단위는 N(뉴턴)으로 주어집니다.
  • 몸무게는 모두 정수입니다.

입출력 예

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

문제 풀이

우선 각 weight가 짝을 이룰 수 있는 모든 경우를 찾아, 테이블(map)에 저장을 해둔다. 이 때, 모든 몸무게는 정수이므로, 정수로 나누어 떨어지지 않는 수는 배제한다. 짝을 찾을 사람의 몸무게를 x, 후보의 몸무게를 y, 각각이 앉을 거리를 a, b 라 하였을 때, ax = by 가 성립해야 한다. a, b는 2, 3, 4 중 하나이고, 따라서 x와 짝이될 후보의 몸무게 y는 아래의 표와 같다.

a, b	2	3	4
2	x * 1	x * (2 / 3)	x * (2 / 4)
3	x * (3 / 2)	x * 1	x * (3 / 4)
4	x * 2	x * (4 / 3)	x * 1

그 뒤, x 와 짝이 될 수 있는 후보의 몸무게가 실제 weights 에 몇명이나 있는지 확인하기 위해, 또 다른 테이블 (map)을 만든다. 예시로 예를 든다면, 다음과 같다.

Weight	100	180	270	360
numOf	2	1	1	1

이제 weights를 순회하면서, 후보에 해당하는 몸무게가 weights에 몇명이나 있는지 확인을 해주고, answer에 더해준다.

모든 weights를 돌게 되면, 순서에 상관있는 짝 (즉, nP2)이 만들어지게 되므로, 2를 나누어 주면 문제가 해결된다.

코드

Java

import java.util.*;

class Solution {

    public long solution(int[] weights) {
        long answer = 0;
        
        Map<Integer, Set<Integer>> pair = setPair(weights);
        Map<Integer, Integer> numOf = setNumOf(weights);

        for (int w : weights) {
            Set<Integer> pairSet = pair.get(w);
            
            for (int p : pairSet) {
                int num = numOf.getOrDefault(p, 0);
                // 만약 현재 몸무게와 후보 몸무게가 같다면 자기 자신 제외
                answer += w == p ? num - 1 : num;
            }
        }
        
        return answer / 2;
    }
    
    // 각 몸무게의 인원수가 담긴 테이블 만들기
    private Map<Integer, Integer> setNumOf(int[] weights) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int w : weights) map.put(w, map.getOrDefault(w, 0) + 1);
        return map;
    }
    
    // 각 몸무게의 짝 후보들이 담긴 테이블 만들기
    private Map<Integer, Set<Integer>> setPair(int[] weights) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        
        for (int w : weights) {
            if (map.containsKey(w)) continue;
            map.put(w, getPairsOf(w));
        }
        
        return map;
    }
    
    //모든 후보 몸무게 구하기
    private Set<Integer> getPairsOf(int weight) {
        Set<Integer> set = new HashSet<>();
        
        for (int i = 2; i <= 4; i++) {
            for (int j = 2; j <= 4; j++) {
                if ((i * weight) % j == 0) set.add((i * weight) / j);
            }
        }
        
        return set;
    }
}