[Algorithm] Programmers_시소 짝꿍 in Java

💡 Programmers Lv2. 시소 짝꿍:

주어진 몸무게 배열을 두고 시소 짝꿍 찾기

🌱 코드 in Java

알고리즘: DP[?]

public class Solution {
    public long solution(int[] weights) {

        Long answer = Long.valueOf(0);
        
        int[] w = new int[1001]; // 기존 몸무게별 사람수 카운팅 배열
        int[] wd = new int[4001]; // 가중치 몸무게별 카운팅 배열, 짝꿍의 수

        for(int i = 0; i < weights.length; i++)
        {
            int d2 = weights[i]*2; 
            int d3 = weights[i]*3;
            int d4 = weights[i]*4;

            answer += wd[d2]; // 해당 가중치 무게와 동일한 짝꿍의 수 더하기
            answer += wd[d3];
            answer += wd[d4];

            if(w[weights[i]] > 0) // 같은 몸무게가 이전에 있었다면
                answer -= w[weights[i]] * 2; // answer에 3배가 저장되었기 때문에 2배를 빼주어야함

            w[weights[i]]++; // 현재 탐색하는 무게 카운팅
            wd[d2]++;
            wd[d3]++;
            wd[d4]++;
        }
        return answer;
    }
}

이번 문제는 솔직히 내 힘으로 못 풀었다.
이것저것 건들여보았으나 시간초과 등등의 문제로 포기하고
다른 사람의 풀이를 찾아서 풀었다

그리고 이 풀이를 보고 하.. 진짜 이런 생각 어케함 🤦🏻‍♀️ 하고 잠시 대가리 빡빡침.

암튼, 저 풀이를 보면서 느낀건

1. weights의 길이가 엄청 기니 시간초과 문제가 발생할 수 있다 -> 따라서 한 번 배열을 훑으면서 끝낼 수 있는 방법을 찾자
2. 기존 몸무게별 사람수 카운팅 배열과 가중치 몸무게별 카운팅 배열을 달리 하여, 가중치 몸무게별 카운팅 배열을 통해서 같은 몸무게가 되는 짝꿍의 수(나 이전에 해당 가중치 몸무게에 카운팅 된 수만큼이 나와 짝꿍이 되는 것이기 때문에 그만큼 answer에 넣어주면 된다.)를 구하고, 기존 몸무게가 똑같을 경우 3가지 경우에서 다 합산이되니 기존 몸무게가 같은 사람의 수를 카운팅한 배열에서 사람수 * 2배를 다시 answer에서 빼주자

이런 생각의 흐름으로 문제를 풀 수 있다는 것이다.

진짜.. 이런 생각 어케함..

100, 100, 50, 100과 같은 weights배열이 있다고 할 때,
마지막 100을 탐색하는 경우에 wd[200]에는 3이 들어있겠지만
이 3을 나누어 생각하면 100 2 = 200 2개와, 50 4 = 200 1개가 들어있는 것과 같다.
이걸 나누어 놓은 것이 w배열과 wd배열인 것이다.

나도 문제를 보면서 이런 풀이가 빠릿하게 떠올랐음 좋겠다

🧠 기억하자

1. 문제의 조건을 잘 보자

• 무게는 100 <= x <= 1,000 사이이다. 따라서 가중치 무게도 4,000을 넘지 않기 때문에 wd[4001]의 공간을 할당하면 된다.