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

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

프로그래머스

2023.11.06 - [분류 전체보기] - [Java] 프로그래머스 - N개의 최소공배수

[Java] 프로그래머스 - N개의 최소공배수

 

최초 코드의 최대공약수 구하는 로직은 위 포스팅을 참고했다.

최초 코드

import java.util.Arrays;

class Solution {
    private int[][] results;
    private static final int MAX_WEIGHT=1001;
    
    public long solution(int[] weights) {
        results = new int[MAX_WEIGHT][MAX_WEIGHT];
        long answer = 0;
        
        for(int i=0; i<weights.length-1; i++){
            for(int j=i+1; j<weights.length; j++){
                int person1 = weights[i];
                int person2 = weights[j];
                
                //서로 몸무게가 같으면 ++
                if(person1==person2){
                    answer++;
                    continue;
                }
                //계산 전이면
                if(results[person1][person2]==0){
                    int gcd = calcGcd(person1, person2);
                    int[] res = new int[]{person1/gcd, person2/gcd};
                    Arrays.sort(res);
                        
                    if((res[0]==1&&res[1]==2)||(res[0]==2&&res[1]==3)||(res[0]==3&&res[1]==4)){
                        results[person1][person2] = 1;
                        results[person2][person1] = 1;
                        answer++;
                    }else{
                        results[person1][person2] = -1;
                        results[person2][person1] = -1;
                    }
                    continue;
                }
                //이전 계산 결과 시소 짝꿍이 아닌 경우
                if(results[person1][person2]==-1){
                    continue;
                }
                //이전 계산 결과 시소 짝꿍인 경우
                answer++;
            }
        }
        return answer;
    }
    
    private int calcGcd(int num1, int num2){
        int gcd=num1%num2;
        if(gcd==0){
            return num2;
        }
        return calcGcd(num2, gcd);
    }
}

 

1차 개선(정렬 + 가지치기)

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    private int[][] results;
    private static final int MAX_WEIGHT=1001;
    
    public long solution(int[] weights) {
        results = new int[MAX_WEIGHT][MAX_WEIGHT];
        long answer = 0;
        
        Arrays.sort(weights);
        
        for(int i=weights.length-1; i>0; i--){
            for(int j=i-1; j>=0; j--){
                int weighter = weights[i];
                int smaller = weights[j];
                
                //** 가지치기
                if(weighter>smaller*2){
                    break;
                }
                //서로 몸무게가 같으면 ++
                if(weighter==smaller){
                    answer++;
                    continue;
                }
                //계산 전이면
                if(results[weighter][smaller]==0){
                    int gcd = calcGcd(weighter, smaller);
                    int[] res = new int[]{weighter/gcd, smaller/gcd};
                    Arrays.sort(res);
                        
                    if((res[0]==1&&res[1]==2)||(res[0]==2&&res[1]==3)||(res[0]==3&&res[1]==4)){
                        results[weighter][smaller] = 1;
                        results[smaller][weighter] = 1;
                        answer++;
                    }else{
                        results[weighter][smaller] = -1;
                        results[smaller][weighter] = -1;
                    }
                    continue;
                }
                //이전 계산 결과 시소 짝꿍이 아닌 경우
                if(results[weighter][smaller]==-1){
                    continue;
                }
                //이전 계산 결과 시소 짝꿍인 경우
                answer++;
            }
        }
        return answer;
    }
    
    private int calcGcd(int num1, int num2){
        int gcd=num1%num2;
        if(gcd==0){
            return num2;
        }
        return calcGcd(num2, gcd);
    }
}

일단 최대공약수를 구한 다음 이를 각 몸무게에 나눴을 때 나온 숫자가 1:2, 2:3, 3:4 중 하나라면 시소짝꿍으로 간주했다.

하지만 최대공약수를 구하는 것도 상당한 시간복잡도가 나오기 때문에 다른 방법이 필요했다.

2차 개선(최대공약수 제거, 몸무게 비례식 적용)

import java.util.Arrays;

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        Arrays.sort(weights);
        
        for(int i=weights.length-1; i>0; i--){
            for(int j=i-1; j>=0; j--){
                int weighter = weights[i];
                int smaller = weights[j];
                //** 가지치기
                if(weighter>smaller*2){
                    break;
                }
                //서로 몸무게가 같으면 ++
                if(weighter==smaller){
                    answer++;
                    continue;
                }
                if(isBalanced(weighter, smaller)){
                    answer++;
                    continue;
                }
            }
        }
        return answer;
    }
    
    //** 최대공약수 계산 대체 메서드
    private boolean isBalanced(int w, int s){
        if(w==2*s){
            return true;
        }
        if(2*w==3*s){
            return true;
        }
        if(3*w==4*s){
            return true;
        }
        return false;
    }
    
    //최대공약수 계산 제거
    // private int calcGcd(int num1, int num2){
    //     int gcd=num1%num2;
    //     if(gcd==0){
    //         return num2;
    //     }
    //     return calcGcd(num2, gcd);
    // }
}

 

그렇게 질문하기를 참고했고 위와 같은 계산식으로 대체할 수 있었다.

문제에서 주어진 대로 그대로 적용하면 되는데 예를 들어 각 무게가 180과 270이라고 하면 180:270=2:3이다.

즉 270*2 = 180 * 3이며, 이를 조건식으로 그대로 사용한다면 최대공약수를 굳이 구할 필요가 없게 된다.

smaller는 180 weighter는 270이므로 2*w ==s*3 조건에 걸리게 된다.

 

하지만 개선해도 기본적으로 O(N^2)이기 때문에 큰 입력에서는 통과하지 못하는 모습이다.

N^2을 하지 않고는 문제를 해결할 방법을 찾지 못했기 때문에 해답을 구글링했고 아래의 모범답안을 찾을 수 있었다.

---

모범 답안(정렬, 해시)

import java.util.*;

class Solution {
    public long solution(int[] weights) {
        Arrays.sort(weights);
        Map<Double, Integer> map = new HashMap<>();
        long answer = 0;
        
        for(int e: weights){
            double a = e*1.0;
            double b = (e*1.0)/2;
            double c = (e*2.0)/3;
            double d = (e*3.0)/4;
            
            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(e*1.0, map.getOrDefault(e*1.0, 0)+1);
        }
        
        return answer;
    }
}

 

시나리오

1. weights를 오름차순 정렬한다.

2. 각 요소를 담을 map을 생성한다.

3. weights를 순회한다. 현재 요소가 지금까지의 요소보다 가장 큰 숫자이기 때문에 비례식에서 작은 수를 곱해야 한다.

그렇게 현재 요소 *  1, 현재 요소 / 2, 현재 요소 * 2 / 3, 현재 요소 *3 / 4를 했을 때 map에 이 계산 결과를 key로 갖는 쌍이 있다면 그 쌍의 value만큼 answer에 더한다.

4. map에 현재 요소를 put한다. 단, 현재 요소를 키로 갖는 쌍이 있을 수 있으므로 getOrDefault 메서드를 이용한다.

5. answer반환

 

배열을 오름차순 정렬했기 때문에 앞으로 나올 수들은 현재 요소보다 크거나 같을 수 밖에 없다.

 

만약 정렬을 하지 않는다면 조건식의 수식이 현재 요소가 이전 요소보다 클 때를 기준으로 맞춰져 있기 때문에 오답이 나올 수 밖에 없다. 그렇다면 현재 요소가 이전 요소보다 작을 때의 수식도 작성해놓는다면 정답이 나올 수 있을까? 그렇지 않다. 비교 대상이 불분명해 두 수식 중 어떤걸 사용할지 분기할 수 없고, 그렇기 때문에 두 수식에 해당되는 모든 map요소를 get하기 때문에 중복이 발생할 수 있다.

 

출처: https://mag1c.tistory.com/295

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