[프로그래머스] 시소 짝꿍(Level 2) HashMap

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/152996

1. 문제 요약

• 중심으로부터 2, 3, 4m 위치에 좌석이 있는 시소에 주어진 몸무게들을 가진 인원들의 조합
• 몸무게 조합에서 존재하는 시소쌍의 갯수 구하기.
• 시소쌍 : 시소가 평형이 되게하는 두 값의 쌍.

2. 핵심 아이디어

• 몸무게 등장 수를 세어둔다 (ex: 100이 2명, 180이 1명, 360이 1명, 270이 1명)
• 자기 자신끼리 조합하는 경우 (nC2)
• 특정 거리비율이 성립하는 다른 몸무게와 조합하는 경우 (2:3, 2:4, 3:4)

3. 풀이 코드

public long hashMapSolution(int[] weights){
        long answer = 0;
        Map<Integer, Long> map = new HashMap<>();

        for (int w : weights) {
            map.put(w, map.getOrDefault(w, 0L) + 1);
        }

        for (int w : map.keySet()) {
            long count = map.get(w);

            // 1. 같은 무게끼리 (2:2, 3:3, 4:4)
            if (count >= 2) {
                answer += count * (count - 1) / 2; // nC2 공식. n개 중 2개를 뽑는 경우의 수. n은 같은 무게를 가진 사람의 수.
            }

            // 2. 다른 무게와의 조합
            // w2 = w1 * d1 / d2
            // (2:3)
            if ((w * 2) % 3 == 0 && map.containsKey(w * 2 / 3)) {
                answer += count * map.get(w * 2 / 3);
            }
            // (2:4) == (1:2)
            if (w % 2 == 0 && map.containsKey(w / 2)) {
                answer += count * map.get(w / 2);
            }
            // (3:4)
            if ((w * 3) % 4 == 0 && map.containsKey(w * 3 / 4)) {
                answer += count * map.get(w * 3 / 4);
            }
        }

        return answer;
    }

이중 for문 방식 : 시간초과로 실패

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

        for (int i = 0; i < weights.length; i++) {
            for (int j = i + 1; j < weights.length; j++) {
                long w1 = weights[i];
                long w2 = weights[j];

                // 거리비율 2:2, 2:3, 2:4, 3:2, 3:3, 3:4, 4:2, 4:3, 4:4 검사
                if (w1 == w2 || w1 * 2 == w2 * 2 || w1 * 2 == w2 * 3 || w1 * 2 == w2 * 4
                        || w1 * 3 == w2 * 2 || w1 * 3 == w2 * 3 || w1 * 3 == w2 * 4
                        || w1 * 4 == w2 * 2 || w1 * 4 == w2 * 3 || w1 * 4 == w2 * 4) {
                    answer++;
                }
            }
        }

        return answer;
    }

4. 회고 및 느낀점

• 시소쌍의 개념부터 이해하기 힘들었다.
• HashMap을 통해 연산속도를 최적화 할 수 있다는 것을 코드를 통해 보았다. 단순 2중 for연산은 시간초과로 실패.
• 유사한 유형에 해당 로직을 활용할 수 있도록 익혀야겠다.
•