[구현 or DP]프로그래머스 시소 짝궁(실패분석 - 메모리 초과)

접근

시소짝궁

이 문제는 메모리 초과가 발생하였습니다.
제한사항을 제대로 보도록 노력해야 겠습니다.

2 ≤ weights의 길이 ≤ 100,000
100 ≤ weights[i] ≤ 1,000
몸무게 단위는 N(뉴턴)으로 주어집니다.
몸무게는 모두 정수입니다.

입니다.
제 풀이의 경우 100,000 * 99,999 번의 연산이 발생합니다.
시간 초과와 더불어 메모리 초과가 발생할 수 있습니다.

좀 복잡하게 풀었습니다.
나와 짝궁이 될 수 있는 상대의 몸무게와 나의 몸무게의
최소공배수를 구합니다.

그 최소공배수로 각자의 몸무게를 나눈 후
그 몫의 값에 2,3,4를 곱합 결과값을 다시 Set에 넣고
Set의 크기가 6보다 작으면 중복된 몸무게가 존재하여 상쇄된다고 생각하여 접근하였습니다.

하지만 너무 많은 연산이 발생합니다.

그래서 다른 분의 풀이를 참고하였습니다.

일단 풀이는 Map을 이용한 방법과
Map이 아니라 두 가지 조건을 이용한 풀이가 있습니다.

• Map을 이용한 풀이의 로직

  • 이 풀이는 Map에 저장된 키를 통해 자신과 상쇄된 사람의 수를 value로 저장하는 것이다.
  • 이 풀이는 메모제이션의 방법이라고 생각하면 된다.

• Map을 이용하지 않은 풀이의 로직

  • 1. 오름차순으로 정렬한다.
  • 2. 이전 값과 같은 경우 이전에 상쇄된 사람의 수에 중복된 1회의 값을 제거하여 answer에 누적한다.
  • 3. 이전 값과 같지 않은 경우 2,3,4를 본인과 본인 이후의 값들에 곱해 같은 경우 상쇄되는 사람의 수에 +1을 한다.

메모리 초과인 나의 풀이

import java.util.*;

class Solution {
    
    static ArrayList<Value> list = new ArrayList<>();
    static List<Integer> mm = List.of(2,3,4);
    static class Value {
        int a;
        int b;
        public Value(int a, int b){
            this.a = a;
            this.b = b;
        }
    }
    
    public long solution(int[] weights) {
        long answer = 0;
        
        
        
        //1. 모든 조합의 수 만들기
        //2. 두수가 같은가?
        //3. 같지 않은가? -> 최대 공약수가 존재하는가? -? 두수의 비율이 2보다 작은가?
        
        // 1번 과정
       for(int i=0;i<weights.length-1;i++){
           for(int j=i+1;j<weights.length;j++){
               list.add(new Value(weights[i],weights[j]));
           }
       }
        
        
        for(Value l : list){
            System.out.println("a:"+l.a+",b:"+l.b);
        }
        
      // 2. 만들어진 배열을 검사기
      answer = checkSee(list);
        
        
        
        return answer;
    }
    
    static int checkSee(ArrayList<Value> list){
        int cnt=0;
        for(int i=0;i<list.size();i++){
            if(list.get(i).a == list.get(i).b){
                cnt++;
                System.out.println("같은 경우 a:"+list.get(i).a+",b:"+list.get(i).b);
            }else{
                //1. 최대 공약수 구하기
                int abGcd = gcd(list.get(i).a,list.get(i).b);
               //2. 최소공배수 구하기
                int abLcm = list.get(i).a*list.get(i).b/abGcd;
                //3. 만들 수 있는가 체크하기
                int A = abLcm / list.get(i).a ;
                int B = abLcm/list.get(i).b;
                Set<Integer> set = new HashSet<>();
                for(int m : mm){
                    set.add(A*m);
                    set.add(B*m);
                }
                if(set.size()<6){
                  cnt++;
                }
            }
             
        }
        return cnt; 
        
    }
    static int gcd(int A, int B){
        if(B==0) return A;
        return gcd(B,A%B);
    }
    
  
}

Map을 이용한 풀이- 메모제이션

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

Map을 이용하지 않은 풀이

import java.util.*;

class Solution {
   
    public long solution(int[] w) {
       
        long answer=0;
        Arrays.sort(w);
        
        int len = w.length;
        int zeroP =0;
        for(int i=0;i<len-1;i++){
            // 이전값과 같은 경우 
            if(i>0 && w[i]==w[i-1]){
                // 이전 상쇄된 사람의 수에서 중복된 1회의 연산(100-100)을 마이너스
                zeroP--;
                answer+=zeroP;
                continue;
            }
            zeroP=0;
            for(int j=i+1;j<len;j++){
                if(w[i]==w[j]
                  || w[i]==w[j]*2
                  || w[i]*2 == w[j]
                  || w[i]*3 == w[j]*2
                  || w[i]*2 == w[j]*3
                  || w[i]*3 == w[j]*4
                  || w[i]*4 == w[j]*3
                  ){
                    zeroP++; 
                }
                  
            }//for j
            
            answer+=zeroP;    
        }// for i
        
        
        return answer;
    }
  
}