[프로그래머스] 시소 짝꿍

코드 힌트

1. 빠르게 탐색할 수 있는 자료구조

• 처음 문제를 풀었을 때는 2중 for문을 사용하여 풀었지만, 시간이 많이 소요되어 시간 복잡도 문제가 발생했습니다.
• 빠르게 요소를 찾기 위해 이진 탐색을 사용하는 방법을 고려했습니다.
• 여기서는 HashMap을 사용하여 key는 요소(무게), value는 해당 요소의 빈도로 활용하여 문제를 풀었습니다.

2. 짝꿍 맞추기

• 시소 짝꿍이 되는 조건은 두 무게가 같은 비율일 때입니다.
• 예를 들어, 무게가 2(m), 3(m), 4(m)인 지점에 좌석이 있을 때, 두 좌석 간의 비율이 같으면 짝꿍이 됩니다.
• 즉, w1 * {2, 3, 4} == w2 * {2, 3, 4} 조건 중 하나라도 만족하면 짝꿍을 찾을 수 있습니다.

3. 중복 허용

• 만약 같은 무게를 가진 사람이 여러 명 있으면, 각 쌍을 조합하여 여러 짝꿍을 만들 수 있습니다.
• 예를 들어, 무게가 100인 사람이 3명이라면:
  • [a: 100, b: 100, c: 100]
  • a와 b, a와 c, b와 c가 짝꿍이 되어 총 3번의 짝꿍이 생깁니다.
• 중복된 무게를 효과적으로 관리하는 것이 중요합니다.

4. 타입 관리

• 2, 3, 4(m) 인 지점을 비교할 때 double로 변환한 후 int로 변경을 했을 때 문제가 발생할 수 있습니다.
• 처음부터 무게를 double로 변경하고 진행하시면 수월하게 관리할 수 있습니다.

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public long solution(int[] arr) {
        // weights 배열 생성 (int 배열을 double 배열로 변환)
        double[] weights = new double[arr.length];
        
        // arr 배열의 요소를 weights 배열로 복사
        for (int i = 0; i < arr.length; i++) {
            weights[i] = (double) arr[i];
        }

        // 결과를 저장할 변수
        long result = 0;
        
        // 무게와 해당 무게의 개수를 저장할 HashMap 생성
        Map<Double,Integer> map = new HashMap<>();
        
        // weights 배열을 순회하며 각 무게의 개수를 카운트하여 map에 저장
        for (double weight : weights) {
            map.put(weight, map.getOrDefault(weight, 0) + 1);
        }

        // weights 배열을 정렬하여 오름차순으로 정렬된 무게를 기준으로 탐색
        Arrays.sort(weights);
        
        // 정렬된 weights 배열을 순회하면서 짝꿍을 찾음
        for (double weight : weights) {
            // 현재 weight가 map에서 1인 경우 삭제, 그렇지 않으면 1 감소
            if (map.get(weight) == 1) {
                map.remove(weight);
            } else {
                map.put(weight, map.get(weight) - 1);
            }
            
            // 시소 짝꿍 조건에 맞는 값을 찾아 result에 더함
            // 1. 같은 무게의 개수
            result += map.getOrDefault(weight, 0);
            // 2. 2배의 무게가 있는지 확인
            result += map.getOrDefault(weight * 2, 0);
            // 3. 4/3 배의 무게가 있는지 확인
            result += map.getOrDefault(weight * 4. / 3, 0);
            // 4. 3/2 배의 무게가 있는지 확인
            result += map.getOrDefault(weight * 3. / 2, 0);
        }

        // 최종 결과 반환
        return result;
    }
}