프로그래머스 | LV. 2 시소 짝꿍 - 비례식 활용 문풀 (Java)

⬛ 프로그래머스 | LV. 2 시소 짝꿍 - 비례식 활용 문풀 (Java)

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

프로그래머스

문제 설명

---

💚문제 접근 방식

사람 수가 10만으로 들어오기 떄문에 이중for문을 돌면 반드시 시간초과가 뜬다. 효율적인 풀이로 접근해야 한다.

첫 시도 | 최대 공약수, DFS로 풀이 시도

• 매번 두 수에 대한 최대 공약수를 구해서 두 값에 대한 최대 공약수로 나눈 몫이 1, 2, 3, 4 에 포함되는지 확인하는 식으로 풀었다.
• 수의 중복을 막기 위해 HashMap을 활용해서 중복을 제거했고 중복이 제거된 몸무게 종류에 대해서만 DFS를 돌아 중복되지 않는 두 가지 값에 대해 처리하려고 했다.
• 이게 문제가 됐던 이유는 결국 모든 (두 수)에 대한 비교를 처리하면서도 비교의 중복도 막아줘야 했는데 그게 잘 안돼서였다. DFS로 중복되지 않는  nCr 조합을 시도 했는데 ex. [100,200] 과 [200,100]처럼.. 두 수가 중복되지 않는 완벽한 조합 처리가 안됐다. 

 

두번째 시도 | 비례식 활용

풀이를 찾아보고 비례식을 활용해야 한다는 것을 알았다.

[출처] https://youngyin.tistory.com/345

이 문제에서 나올 수 있는 두 수의 2, 3, 4m 떨어진 균형 비례 관계는 위의 표와 같다고 한다.

이때 중복 체크되는 것을 막기 위해서는 1보다 작은 분수 값만 활용한다. (위의 표는 1보다 큰 값만 활용함)

어느 것을 활용하든 상관없지만 그에 맞는 처리를 해주어야 한다.

 

1) 우선 weights배열을 오름차순 정렬시킨다.

→ 정렬을 시켜두면 for문으로 순회할 때마다 map의 key보다 항상 x가 크거나 같기 때문에 기존 map의 Key들에 대하여 매번 1보다 작은 비례식을 활용한 대상값이 존재하는지 확인하기 수월하다.

2) 기존 map에는 오직 weights만 담긴다. 매번 for문을 돌면서 1보다 작은 비례 분수식으로 만든 값이 기존 map에 존재하는지 확인 하고 존재한다면 그 개수만큼 answer를 누적시키는 방식이다.

→ for문으로 매번 x의 1배, 1/2배, 2/3배, 3/4배의 값을 구해두고 기존 map에 존재하는지 확인후 answer를 누적시킨다.

 

💚 제출 코드

import java.util.*;

class Solution {
    //솔루션 함수 
    public long solution(int[] weights) {
        long answer = 0;
        
        Arrays.sort(weights);//정렬 해야 뒤에 오는 값이 차례대로 처리 된다.
    
        Map<Double, Integer> map = new HashMap<>();
        
        for(int x : weights){
            //현재값
            double a = x * 1.0;
            //에 대한 타겟값 미리 계산
            double b = (x * 1.0) / 2.0;
            double c = (x * 2.0) / 3.0;
            double d = (x * 3.0) / 4.0;
            
            //기존 map에 담긴 게 있다면 answer에 개수 누적 
            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);
            
            System.out.println(answer);
            //현재의 val도 map에 담음
            map.put(a, map.getOrDefault(a, 0)+1);
        }
        

        return answer;
    }
}