[프로그래머스/Java] 시소 짝궁

 

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

프로그래머스

weights의 길이가 10만이나 되므로 단순히 weights에 대해서 2명을 선택하는 조합을 써서 비율을 확인하는 방식으로 문제를 해결하려고 했다면 시간 초과가 걸립니다. 그래서 어떻게 하면 효율적으로 비율을 검증할 수 있을지 잘 캐치하는 것이 중요한 문제입니다.

 

고찰 과정

문제의 예시 힌트를 바탕으로 과정을 생각했습니다. 문제 해결에 대한 고찰 순서는 다음과 같습니다.

1. 먼저 예시를 바탕으로 거리 비율을 계산했다.
   -> (100, 100)의 비율 = 1:1
   -> (180, 360)의 경우 거리 비율 => 1:2이므로 이는 곧 2:4가 존재하므로 성립
   -> (180, 270)의 경우 거리 비율 => 2:3이므로 성립
   -> (270, 360)의 경우 거리 비율 => 3:4이므로 성립 (약분하면 3:4가 나온다.)
2. 최대공약수로 나누어서 양쪽으로까지 시소의 각 거리 (2m, 3m, 4m) 중 두 개의 값이 모두 나오면 시소 짝궁이 성립하지만 이 때는 조합을 쓰게 되므로 최대공약수에 대한 생각은 접었다.
3. 2m, 3m, 4m로 나올 수 있는 비율의 경우를 생각해보았다. 나올 수 있는 경우는 다음과 같다.
   -> (1, 1), (2, 3), (1, 2), (3, 4)
   -> 위 비율의 경우를 담는 배열 ratios 배열을 하나 만든다.
4. HashMap을 활용하여 각 몸무게에 대한 출현 빈도 정보를 저장한다.
5. map에서 각 몸무게를 하나씩 살펴가며 ratios 배열을 활용하여 나올 수 있는 몸무게의 값을 바탕으로 적절한 연산을 통해서 시소 짝궁의 개수를 구한다.
   -> 상대 몸무게를 구했는데 그 몸무게가 자기 자신과 같은 경우에는 나누기 2를 해줌으로써 짝의 수를 구한다.
   -> 상대 몸무게와 내 몸무게가 다른 경우는 상대 몸무게의 카운트와 내 몸무게의 카운트를 곱해줌으로써 짝의 수를 구한다.

---

코드

import java.util.*;

class Solution {
    
    public long solution(int[] weights) {
        long answer = 0;
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int weight : weights) {
            map.put(weight, map.getOrDefault(weight, 0) + 1);
        }
                
        int[][] ratios = {{1, 1}, {2, 3}, {1, 2}, {3, 4}};
        
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int weight = entry.getKey();
            
            for (int[] ratio : ratios) {
                if ((weight % ratio[0]) > 0) {
                    continue;
                }
                
                int otherWeight = weight / ratio[0] * ratio[1];
                
                if (!map.containsKey(otherWeight)) {
                    continue;
                }
                
                long count = (long)map.get(weight);
                
                if (weight == otherWeight) {
                    answer += count * (count - 1) / 2;
                    continue;
                }
                
                long otherCount = (long)map.get(otherWeight);
                answer += count * otherCount;
            }     
        }
        
        return answer;
    }
}