[프로그래머스] 시소 짝궁

문제

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

프로그래머스

 

문제 분석

[제한 사항]

• 2 ≤ weights의 길이 ≤ 100,000
• 100 ≤ weights[i] ≤ 1,000
  • 몸무게 단위는 N(뉴턴)으로 주어집니다.
  • 몸무게는 모두 정수입니다.

 

시소를 중심으로 2, 3, 4 미터 거리에 좌석이 있고 사람들의 몸무게가 주어 졌을 때 짝궁이 몇 쌍 존재하는 지 구하는 문제이다.

짝궁은 서로 마주 앉았을 때 시소가 균형을 이루는 경우 그 두 사람을 짝궁이라고 한다.

양쪽의 (시소 중심축과 좌석 사이의 거리 X 몸무게) 가 같은 경우 짝궁이다.

문제 접근

 

좌석의 수가 많지 않기 때문에 모든 경우의 수를 따질 수 있었다. 

 

예를들어 몸무게가 100 인 사람이 2번 자리에 앉았을 경우 짝궁 후보로 (100, 100 * 2/3, 100 * 2/4) 이렇게 3명이 된다.

같은 방법을 3번 자리에 앉았을 경우, 4번 자리에 앉았을 경우를 모두 따져 모든 후보를 찾을 수 있고 해당 후보가 해당 후보가 실제 존재한다면 짝궁 수를 늘리면 된다.

 

 모든 경우의 수를 따지면 총 9개가 나오지만 중복 되는 경우를 제거하면 1, 2/3, 2/4, 3/4 4가지 경우의 수가 남는다.

 

weights 배열의 크기가 10^5 이기 때문에 O(n^2) 으로는 풀지 못한다. 

Map 자료구조를 이용하여 한번에 스캔하면서 문제를 풀고 중복되는 무게를 처리하기 위해서 해당 무게가 몇번 등장했는지 횟수도 체크한다.

코드

import java.util.*;

class Solution {
    static final double[] partners = {1.0, 2.0 / 3, 2.0 / 4, 3.0 / 4};
    public long solution(int[] weights) {
        long answer =  0;

        Map<Double, Integer> map = new HashMap<>();

        Arrays.sort(weights);

        for(int weight : weights){
            for (double partner : partners) {
                partner *= weight;

                if(map.containsKey(partner)){
                    answer+=map.get(partner);
                }
            }
            map.put((double) weight, map.getOrDefault((double) weight, 0) + 1);
        }

        System.out.println(map);
        return answer;
    }
}