Programmers - 시소짝궁 with JAVA

 

 

로직

아이디어 : 무게에 (1, 1/2, 2/3, 3/4, 4/3, 3/2, 2)를 곱한 값이 다른 사람들 중 존재한다면 answer += 1 이다.

몰랐던 점 : 같은 무게라도 다른 사람이다. 따라서 Map의 모든 값을 더해줘야한다. 

 

 

 

 

코드 1

- Map을 활용해 메모이제이션한 경우

import java.util.*;
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        double[] times = {1.0, 2.0/4, 3.0/4, 2.0/3, 4.0/3, 3.0/2, 2.0};
        Map<Double, Double> map = new HashMap<>();
        for(double weight : weights) {
            map.put(weight, map.getOrDefault(weight, 0.0)+1);
        }
        for(double weight : weights) {
            map.put(weight, map.get(weight)-1);
            for(double time : times) {
                double target = weight*time;
                if(map.get(target) == null){
                    continue;
                }
                if(map.get(target) == 0){
                    continue;
                }
                answer += map.get(target);
            }
        }
        return answer;
    }
}

 

 

 

코드 2

- 배열으로 메모이제이션한 경우

import java.util.*;
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        double[] values = {1.0, 2/(double)3, 0.5, 1.5, 
                           3/(double)4, 2.0, 4/(double)3};
        int n = weights.length;
        int[] map = new int[1001];
        for(int weight : weights){
            map[weight] += 1;
        }
        for(int weight : weights){
            map[weight] -= 1;
            for(double value : values){
                double now = value*weight;
                if(now != (double)(int)now){
                    continue;
                }
                if(now > 1000){
                    continue;
                }
                if(map[(int)now] >= 1){
                    answer += map[(int)now];
                }
            }
        }
        return answer;
    }
}