[프로그래머스/Lv.2] 시소 짝꿍 - Java

문제

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

프로그래머스

 

 

리뷰

정확성을 맞히기는 어렵지 않고, 효율성을 더 고려해야 하는 문제이다. 2023 카카오 겨울 인턴십 3번 문제였던 주사위 고르기를 풀 때 효율성을 개선했던 방법으로 해결했다.

 

풀이

포인트는 몸무게가 중복인 사람들이 있기 때문에 같은 값에 대해 중복으로 계산하지 않도록 해서 연산 횟수를 줄이는 것이다.

 

주어진 weights를 순회해서 몸무게 각 값에 해당하는 사람이 몇 명인지 counts라는 HashMap 형태로 저장했다.

 

그리고 실제 연산은 HashMap의 Key끼리만 한다. 케이스#1을 예시로 들면, weights가 [100,180,360,100,270]로 주어졌으나, 실제 연산은 중복된 값을 제외한 [100, 180, 270, 360]끼리만 하는 것이다. 이후 Value로 저장되어 있는 중복된 사람 수만큼 곱해주면 된다.

 

Key 배열을 오름차순으로 정렬하는 이유는 앞에 있는 수가 뒤에 있는 수보다 반드시 작다는 것이 보장하면 3:2, 4:3, 2:1인지만 확인하면 되기 때문이다. 즉, 2:3, 3:4, 1:2인지는 확인하지 않아도 된다.

 

또한 counts에서 Value가 2 이상이면 몸무게가 같은 사람들이 중복으로 존재한다는 것을 의미한다. 이 사람들은 어떻게 조합하든 시소 짝꿍이 될 수 있으므로 value*(value-1)/2를 answer에 더해준다.

 

 

코드

import java.util.*;

class Solution {

    int n;

    public long solution(int[] weights) {
        long answer = 0;

        n = weights.length;

        Map<Integer, Integer> counts = new HashMap<>();

        for(int i = 0; i < n; i++) {
            counts.put(weights[i], counts.getOrDefault(weights[i], 0) + 1);
        }


        int[] countsKeys = counts.keySet().stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(countsKeys);

        for(int i=0;i<countsKeys.length;i++){
            int left = countsKeys[i];
            long leftCount = counts.get(left);
            if(leftCount > 1) {
                answer += leftCount*(leftCount-1) / 2;
            }
            for(int j=i+1;j<countsKeys.length;j++){
                int right = countsKeys[j];
                long rightCount = counts.get(right);
                if(left*3 == right*2 || left*4 == right*3 || left*2 == right) {
                    answer+=leftCount * rightCount;
                }
            }
        }

        return answer;
    }
}