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

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

최소공배수 계산 -> 시간 초과 및 전체적인 통과 실패

• 길이가 100,000이다보니 2중 for문을 통해서 계산을 하게 되면 시간초과가 발생한다.

실패한 코드

package org.example.programers.p152996;

import java.util.Arrays;

public class Main {
}

/**
 * 시소 짝궁
 * 생각한거 : 최송공배수를 이용한 구현
 * 2중 for문이 돌기 때문에 시간초과 발생
 */
class Solution {
    public long solution(int[] weights) {
        long answer = 0;

        Arrays.sort(weights);
        for (int idx = 0; idx < weights.length; idx++) {
            int per1 = weights[idx];
            for (int next = idx + 1; next < weights.length; next++) {
                int per2 = weights[next];
                //값이 같은경우 끝
                if(weights[idx] == weights[next]){
                    answer+=1;
                }else{
                    int lcm = per1 * per2/gcd(per1,per2);
                    if(lcm/per1 <= 4 && lcm/per2 <= 4){
                        answer+=1;
                    }
                }
            }
        }


        return answer;
    }

    private int gcd(int a, int b) {
        if(a % b == 0)
            return b;

        return gcd(b,a%b);
    }
}

다른분의 풀이를 보고 하였습니다.

2시간정도 풀어봤지만 도저히 생각히 나지 않아서 다른분의 풀이를 봤습니다.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
}

/**
 * 시소 짝궁
 * 생각한거 : 최송공배수를 이용한 구현
 * 2중 for문이 돌기 때문에 시간초과 발생
 * weight의 크기가 100 ~ 1000으로 제한되어있다.
 * Map을 통해서 중복 체크
 * 정렬후 값들을 2/3, 2/4 , 3/4 로 값을 체크 하고 있는경우 누적값을 더해준다.
 */
class Solution {
    public long solution(int[] weights) {
        long answer = 0;

        Arrays.sort(weights);
        Map<Double,Integer> map = new HashMap<>();
        for(int num : weights){
            double a = num*1.0;
            double b = (num*2.0)/3.0;
            double c = (num*2.0)/4.0;
            double d = (num*3.0)/4.0;

            if(map.containsKey(a)) answer+= map.get(a);
            if(map.containsKey(b)) answer+= map.get(b);
            if(map.containsKey(c)) answer+= map.get(c);
            if(map.containsKey(d)) answer+= map.get(d);
            map.put((num*1.0),map.getOrDefault((num*1.0),0)+1);
        }


        return answer;
    }

}

//출처

https://mag1c.tistory.com/295