[Algorithm_Java] 시소 짝궁 (Success)

프로그래머스

🙂 확인 사항

1. 무게 중심 구하기: 경우의수 7개 

2. 2중 for문: 약 100,000* 100,000 = 약 100억

3. 1억 기준 약 1초 -> 100억 100초

 

🚨 시간 초과 실패

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        
        for(int i=0; i<weights.length; i++){
            for(int j=i+1; j<weights.length; j++){
                if(weights[i]==weights[j]){
                    answer++;
                    continue;
                }
                if((2*weights[i]==3*weights[j]) || (3*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((2*weights[i]==4*weights[j]) || (4*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((3*weights[i]==4*weights[j]) || (4*weights[i]==3*weights[j])){
                    answer++;
                    continue;
                }
            }
        }
        
        return answer;
    }
}
 

 

🚨 정렬을 통해 조건을 줄였지만, 시간 초과 실패

import java.util.Arrays;
 
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        
        Arrays.sort(weights);
        
        for(int i=0; i<weights.length; i++){
            for(int j=i+1; j<weights.length; j++){
                if(weights[i]==weights[j]){
                    answer++;
                    continue;
                }
                if((3*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((4*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((4*weights[i]==3*weights[j])){
                    answer++;
                    continue;
                }
            }
        }
        
        return answer;
    }
}
 

 

🚨 정렬을 통해 조건을 줄이기 + 탐색 범위 좁히기, 시간 초과 실패

import java.util.Arrays;
 
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        
        Arrays.sort(weights);
        
        for(int i=0; i<weights.length-1; i++){
            for(int j=i+1; j<weights.length; j++){
                if(2*weights[i]<weights[j]){
                    break;
                }
                if(weights[i]==weights[j]){
                    answer++;
                    continue;
                }
                if((3*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((4*weights[i]==2*weights[j])){
                    answer++;
                    continue;
                }
                if((4*weights[i]==3*weights[j])){
                    answer++;
                    continue;
                }
            }
        }
        
        return answer;
    }
}
 

 

 

😮 찾아본 풀이

import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
 
class Solution {
    
    public long solution(int[] weights) {
        long answer = 0;
 
        Map<Double, Integer> map = new HashMap<>();
 
        Arrays.sort(weights);
        
        for(int weight : weights) {
            double sameWeight = weight*1.0;
            double twoThirdWeight = (weight*2.0)/3.0;
            double halfWeight = (weight*1.0)/2.0;
            double threeQuaters = (weight*3.0)/4.0;
            if(map.containsKey(sameWeight)) answer += map.get(sameWeight);
            if(map.containsKey(twoThirdWeight)) answer += map.get(twoThirdWeight);
            if(map.containsKey(halfWeight)) answer += map.get(halfWeight);
            if(map.containsKey(threeQuaters)) answer += map.get(threeQuaters);
            map.put((weight*1.0), map.getOrDefault((weight*1.0), 0)+1);
        }
 
        return answer;
 
    }
}
 

1. Arrays.sort(weights)

    - weights 오름차순 정렬

2. double sameWeight, twoThirdWeight, halfWeight, threeQuaters

    - weight가 오름차순 정렬되었으므로, 앞의 값과 비교하는 for문은 현재 weight보다 작은 특정 비율을 갖고 있는지만 확인하면 됨

3. map.put((weight*1.0), map.getOrDefault((weight*1.0), 0)+1)

    - weight값을 map에 저장하되, 중복이 제거되므로 이를 해결하기 위해 value 활용

    - 마지막에 위치시켜 자기자신과 비교한 값이 검사되지 않도록 함

        - 만일 맨 위로 위치시킬 경우, 자기 자신과 sameWeight로 비교된 부분을 제거하기 위해 weights.length를 차감해야 함

 

class Solution {
    
    public long solution(int[] weights) {
        long answer = 0;
        
        int[] weightCount = new int[1001];
 
        for(int weight : weights){
            weightCount[weight]++;
        }
        
        for(int weight=100; weight<=1000; weight++){
            long count = weightCount[weight];
            
            if(count==0){
                continue;
            }
            
            answer += count * (count-1) / 2;
            // 동일한 값이 2개 이상일 경우
            
            if (weight * 3 % 2 == 0 && weight * 3 / 2 <= 1000) {
                answer += count * weightCount[weight * 3 / 2];
                // weight: 임의의 수 = 2 : 3
            }
            
           if (weight * 4 % 2 == 0 && weight * 4 / 2 <= 1000) {
                answer += count * weightCount[weight * 4 / 2];
               // weight: 임의의 수 = 2 : 4
            }
 
            if (weight * 4 % 3 == 0 && weight * 4 / 3 <= 1000) {
                answer += count * weightCount[weight * 4 / 3];
                // weight: 임의의 수 = 3 : 4
            }
        }
        
        return answer;
 
    }
}
 

1. int[] weightCount = new int[1001]

    - weight를 index로 사용하고 count를 value로 사용

2. long count = weightCount[weight]

    - count 자체를 int 범위이지만, 동일한 값의 개수를 구하기 위한 공식에서 int * int가 int의 범위를 넘어 long으로 선언

    - 또는 count간의 곱에서 casting을 할 수도 있음

        - 예: 100이 100,000개 있을 때, answer = 100,000* 99,999 > int값의 범위

3. if (weight * 3 % 2 == 0 && weight * 3 / 2 <= 1000)

    - weight * 3 % 2 == 0: weight보다 (3/2)배 더 크지만,

    - weight * 3 / 2 <= 1000: arrayIndexOutOfBoundsException 방지

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

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