시소 짝꿍

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

프로그래머스

 

문제 풀이

 

 n이 최대 100,000이라 완전탐색은 시간 초과이다.

 

두 사람 A(무게 a, 거리 da), B(무게 b, 거리 db)가 짝꿍이려면 [a * da = b * db]가 성립해야 한다. 더 가벼운 짝꿍만을 찾으면서 순회한다면 중복 없이 짝꿍이 성립하는 경우의 숫자를 찾을 수 있다. 더 가벼운 짝꿍을 찾는 거리 조합은 (2,3), (2,4), (3,4) 세 가지 이다.

 

몸무게가 같은 사람끼리는 무조건 시소 짝꿍이다. (nC2를 통해 따로 더해준다.)

 

 

작성한 코드

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        
        // 해당 몸무게를 가진 사람 카운트 (100 ~ 1000)
        int[] count = new int[1001];

        for (int w : weights) {
            count[w]++;
        }

        // 거리 조합 (더 가벼운 상대만 찾는다)
        int[][] ratios = {{2, 3}, {2, 4}, {3, 4}};
        
        for (int w = 100; w <= 1000; w++) {
            if (count[w] == 0) continue;
            
            // 같은 몸무게끼리 짝꿍이 되는 경우 (nC2)
            long c = count[w];
            answer += c * (c - 1) / 2;
            
            // 더 가벼운 짝꿍을 찾는 경우
            for (int[] r : ratios) {
                int da = r[0], db = r[1];
                
                // 짝꿍 = w * da / db
                if ((long) w * da % db == 0) {
                    int partner = (int) ((long) w * da / db);
                    if (partner >= 100 && partner <= 1000) {
                        answer += (long) count[w] * count[partner];
                    }
                }
            }
        }
        
        
        
        return answer;
    }
}