시소 짝꿍 [JAVA]

문제 분석

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

프로그래머스

시소 중앙에서 2,3,4 미터 떨어져 있을 수 있고 왼쪽과 오른쪽의 무게는 거리*앉은 사람의 무게로 정해진다.

각 사이드엔 한명만 시소를 탄다고 할 때, 시소가 균형을 이룬다면, 즉, 왼쪽과 오른쪽은 곱의 크기가 같다면 균형을 이룬다.

이때, 균형을 이루는 쌍의 수를 구하라.

 

무게 자체가 1000밖에 되지 않는다. 따라서, *4를 해도 4000정도다.

따라서, 각 무게의 곱을 배열의 인덱스로 해서 저장하고

무게 자체 또한 별도의 배열에 저장한다.

 

그 후, 주어진 무게 배열을 순회하며

i번째 무게*2, *3, *4에 해당하는 곱배열의 원소의 수 -1(자신)를 구할 수 있다. 즉, 자신 말고 해당 무게를 곱으로 하는 원소들을 찾을 수 있게 된다.

a != b라면 xa=yb 주어진 2,3,4 중 이 식을 만족하는 x와y는 한쌍밖에 없다.

 

다만, a == b 라면 모두 만족하기에 무게 자체를 저장했던 배열을 이용해서 중복해서 더해줬던 2가지 쌍을 다시 빼줘야 한다.

 

마지막으로 구현 자체를 서로 중복되지 않는 쌍을 센게 아닌 모든 쌍을 구하였으니, 즉, i번째 원소와 i+1번째 원소가 서로 쌍을 이뤘다면 i+1번째 원소 검사시에도 i번째 원소와 쌍을 카운트 했기 때문에

구한 쌍의 갯수에서 2를 나눈 값을 리턴해준다.

 

코드

class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        int[] weightInfo = new int[4001];
        int[] originWeightInfo = new int[1001];
        // Set<Integer> multiWeightSet = new HashSet<>();
        for(int i=0; i<weights.length ; i++){
            weightInfo[weights[i]*2]++;
            weightInfo[weights[i]*3]++;
            weightInfo[weights[i]*4]++;
            originWeightInfo[weights[i]]++;
        }
        
        for(int i=0; i<weights.length; i++){
            answer += (weightInfo[weights[i]*2]-1) + (weightInfo[weights[i]*3]-1) + (weightInfo[weights[i]*4]-1);
            answer -= (originWeightInfo[weights[i]]-1)*2;
        }
        return answer/2;
    }
}