[프로그래머스] 시소 짝꿍 (Java)

시소 짝꿍

Level 2

 

문제 설명

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

---

제한 사항

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

---

입출력 예

---

🙅🏻‍♂️ 첫 번째 소스코드 (실패)

import java.util.*;

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

        Map<Integer, int[]> toque = new HashMap<>();

        // weights에 해당하는 2, 3, 4 토큐값을 초기화
        for (int i = 0; i < weights.length; i++) {
            int target = weights[i];

            if (toque.get(target) == null) {
                int[] temp = new int[]{target * 2, target * 3, target * 4};
                toque.put(target, temp);
            }
        }

        for (int i = 0; i < weights.length - 1; i++) {
            for (int j = i + 1; j < weights.length; j++) {
                if (checkDuplicate(
                    toque.get(weights[i]), toque.get(weights[j]))) {
                    answer++;
                }
            }
        }

        return answer;
    }

    public boolean checkDuplicate(int[] x, int[] y) {
        for (int i = 0; i < x.length; i++) {
            for (int j = 0; j < y.length; j++) {
                if (x[i] == y[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

 

테스트 케이스 6번부터 15번까지 모두 시간 초과로 실패를 했다. 아마도 무작정 반복문을 사용하려고 했기 때문인 거 같다. 다른 방법을 한번 찾아봐야할 거 같다.

---

🙆🏻‍♂️ 최종 소스코드

반복문은 총 1번만 돌아야 해당 문제를 성공시킬 수 있다.

import java.util.*;

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

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

        double[] divide = new double[]{
            1.0, 2.0/3, 1.0/2, 3.0/4
        };

        Arrays.sort(weights);
        for (int weight : weights) {
            for (double d : divide) {
                if (map.containsKey(weight * d)) {
                    answer += map.get(weight * d);
                }
            }
            map.put((double)weight, map.getOrDefault((double)weight, 0) + 1);
        }

        return answer;
    }
}

---

🕵🏻 문제 풀이전략

1. divide 배열을 보면 1, 2/3, 1/2, 3/4가 들어가 있다. 이 부분부터 설명을 해야될 것 같다.
   • weights를 정렬을 하고나서 숫자 a, b를 뽑는다고 하면 a는 b보다 같거나 무조건 작을 것이다. 이 부분을 이용한다.
   • 2m, 3m, 4m의 거리가 있을 때, 큰 수인 b를 뽑았을 때 a가 될 수 있는 경우를 생각해본다.
     • a == b → b * 1 == a
       • 이 조건은 a와 b가 같을 때의 조건이다.
         
         
     • a * 3 == b * 2
       • a가 3m에 있고, b가 2m에 있을 때의 조건이다.
       • 다르게 표현하면, b * (2/3) == a 가 된다.
         
         
     • a * 4 == b * 2 → b * (2/4) == a → b * (1/2) == a
     • a * 4 == b * 3 → b * (3/4) == a
   • 즉, 위에서 말한 1, 2/3, 1/2, 3/4는 큰 수 b를 뽑았을 때, 짝궁이 될 수 있는 a를 찾기위한 비율 값이다.
     
     
     
2. weights가 [100, 100, 180, 270, 360] 일 때를 생각해보자. (정렬 후의 상태)
   • b == 100일 때
     • a가 될 수 있는 값은 [100, 50, 75] 이다. 100 * (2/3)의 경우에는 정수가 아니기 때문에 적지 않겠습니다.
     • 이제 map에서 100, 50, 75에 해당하는 무게가 이전에 존재했었는지, 존재했다면 몇 명이나 있었는지 확인합니다.
     • 만약 이전에 해당하는 무게가 존재했었다면, 몇 명이나 존재했는지에 대한 값을 answer에 더해줍니다.
       • 만약 이전에 100이 2명, 75가 3명이었다면, 우리가 뽑은 b = 100인 사람은 총 5명과 짝꿍이 될 수 있기 때문입니다.
         
         
     • 그리고 마지막에는 map에 이미 100이라는 key를 가진 데이터가 있으면 그 key 값에 해당하는 value를 가져와서 1을 더한 후 다시 넣어줍니다. (본인을 1명 추가하는 작업)
     • map에 100이라는 key가 없었다면, 1이라는 값으로 초기화합니다. (자신이 100무게 중에는 최초의 사람)
       
       
       
3. 2번 과정을 반복하면 답을 얻을 수 있습니다.