알고리즘 문제 풀이 - 시소 짝꿍

문제 설명

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

제한 사항

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

---

문제 접근 방법 - 1

• weights 배열에서 두 사람이 특정한 거리 비율로 시소를 탈 때 균형을 이루는 경우를 찾아야 한다.
• 완전 탐색 방법으로는 O(N^2)의 시간 복잡도가 발생하므로 비효율적이기 때문에 HashMap 또는 배열을 활용한 카운팅을 사용하여 O(N) 또는 O(N log N) 으로 해결한다.

완성 코드 - 1 : 실패 (52.9%)

import java.util.HashMap;
import java.util.Map;

public class Test_62_SeesawPartners {
    public long solution(int[] weights) {
        long answer = 0;
        Map<Integer, Integer> weightCount = new HashMap<>();

        // 몸무게 등장 횟수 세기
        for (int weight : weights) {
            weightCount.put(weight, weightCount.getOrDefault(weight, 0) + 1);
        }

        // 가능한 시소 짝꿍 비율
        int[][] ratios = {{1, 1}, {2, 3}, {1, 2}, {3, 4}};

        // 몸무게별 조합 확인
        for (int weight : weightCount.keySet()) {
            int count = weightCount.get(weight);

            // 같은 몸무게끼리 짝꿍 (nC2 = n * (n-1) / 2)
            if (count > 1) {
                answer += (long) count * (count - 1) / 2;
            }

            // 다른 몸무게와 짝꿍 확인
            for (int[] ratio : ratios) {
                int pairWeight = weight * ratio[1] / ratio[0];
                if (pairWeight != weight && weightCount.containsKey(pairWeight)) {
                    answer += (long) count * weightCount.get(pairWeight);
                }
            }
        }

        return answer;
    }
}

• weight * ratio[1] / ratio[0]에서 정수 나눗셈이 발생하며, 값이 정확히 맞지 않을 수 있음
• 같은 짝을 두 번 계산하는 경우가 발생할 수 있음
• for (int weight : weightCount.keySet()) 내부에서 weightCount.containsKey(pairWeight)를 사용하는 방식은 O(1) 이지만, 불필요한 중복 계산이 발생할 가능성이 있음

---

문제 접근 방법 - 2

• 정수 연산만 수행하여 정확성을 높임
• 배율별 곱셈을 미리 계산해 중복 연산을 줄임
• 몸무게 리스트를 정렬 후 중복 제거하며 탐색

완성 코드 - 2

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Test_62_SeesawPartners {
    public long solution(int[] weights) {
        long answer = 0;
        // 정렬하여 중복 탐색을 줄임
        Arrays.sort(weights); 
        Map<Integer, Integer> countMap = new HashMap<>();

        // 몸무게 등장 횟수 카운팅
        for (int weight : weights) {
            countMap.put(weight, countMap.getOrDefault(weight, 0) + 1);
        }

        // 같은 몸무게끼리 짝꿍 만들기 (nC2 = n * (n-1) / 2)
        for (int weight : countMap.keySet()) {
            int count = countMap.get(weight);
            if (count > 1) {
                answer += (long) count * (count - 1) / 2;
            }
        }

        // 시소 균형을 이루는 배율 (1:1 제외)
        int[][] ratios = {{2, 3}, {1, 2}, {3, 4}};

        // 다른 몸무게와 짝꿍 찾기
        for (int weight : countMap.keySet()) {
            int count = countMap.get(weight);

            for (int[] ratio : ratios) {
                int num = weight * ratio[1];
                int den = ratio[0];
                
				// 정수 값이 아닐 경우 무시
                if (num % den != 0) continue;  

                int pairWeight = num / den;
                if (pairWeight != weight && countMap.containsKey(pairWeight)) {
                    answer += (long) count * countMap.get(pairWeight);
                }
            }
        }

        return answer;
    }
}