프로그래머스 - 시소 짝꿍

프로그래머스 - 시소 짝꿍

몸무게의 배열이 주어지고, 정해진 비율에 맞는 쌍(시소의 균형을 유지할 수 있는 짝꿍)의 개수를 찾는 문제입니다. 시간복잡도가 관건인 문제로, 끝내 못 풀고 다른 분의 도움을 받았습니다.

처음에 작성한 코드입니다. 몸무게를 작은 순으로 정렬하고, 낮은 무게부터 올라가며 짝꿍을 찾다가 최대 비율을 초과하면 무게를 올리는 방식으로 시도했지만 시간초과가 났습니다.

import java.util.*;

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        double[] ratio = {1, (double) 4/3, (double) 3/2, 2};
        Arrays.sort(weights);
        
        for (int f = 0; f < weights.length - 1; f++) {
            for (int b = f + 1; b < weights.length; b++) {
                int cur = isValanced(weights[f], weights[b], ratio);
                
                if (cur == 1) {
                    answer += 1;
                    continue;
                }
                if (cur == -2) {
                    break;
                }
            }
        }
        
        return answer;
    }
    
    public int isValanced(int small, int large, double[] ratio) {
        for (int i = 0; i < ratio.length; i++) {
            if (small * ratio[i] == large) {
                return 1;
            }
        }
        if (small * ratio[3] < large) {
            return -2;
        }
        return -1;
    }
}

아래는 https://yejin72.tistory.com/109 을 바탕으로 작성한 코드입니다.

몸무게를 읽어가며 무게마다 몇 명이 있는지 dictionary에 저장하는 방식입니다. 다만, 저장하기 전에 지금까지 내 짝꿍이 몇 명 있었나 확인해서 answer에 추가 후 저장합니다. 이 방식은 빠르면서도, 무게가 같은 쌍을 중복 없이 셀 수도 있어서 인상적이었습니다.

import java.util.*;

class Solution {
    public long solution(int[] weights) {
        HashMap<Double, Integer> hashMap = new HashMap<>();
        long answer = 0;
        double[] ratio = {1, (double) 4/3,
        		(double) 3/2, (double) 3/4, (double) 2/3, (double) 1/2, 2};
        
        for (int i = 0; i < weights.length; i++) {
            for (int j = 0; j < 7; j++) {
                if (hashMap.get((double) weights[i] * ratio[j]) == null) {
                    hashMap.put((double) weights[i] * ratio[j], 0);
                }
                answer += hashMap.get((double) weights[i] * ratio[j]);
            }
            hashMap.put((double) weights[i], hashMap.get((double) weights[i]) + 1);
        }
        
        return answer;
    }
}