[프로그래머스] 시소 짝궁 자바(Java)

문제 설명

 

 

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.

이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.

사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

 

 

---

 

제한사항

 

 

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

 

---

 

입출력 예

 

 

weights	result
[100, 180, 360, 100, 270]	4

 

 

입출력 예 설명

 

{100, 100} 은 서로 같은 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 360} 은 각각 4(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 270} 은 각각 3(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{270, 360} 은 각각 4(m), 3(m) 거리에 마주보고 앉으면 균형을 이룹니다.

 

---

 

코드 설명

 

 

시소 짝궁이 될 수 있는 경우는 총 4가지입니다. 두 weight를 각각 A, B라고 할 때

 

i) A = B

ii) A * 3 = B * 2

iii) A * 4 = B * 2

iv) A * 4 = B * 3

 

이에 따라 이중 반복문을 사용하여 풀이해보았는데요, 가능은 하지만 아무래도 시간이 오래 걸리기 때문에 좋은 방법은 아닌 것 같습니다.

 

 

import java.util.Arrays;
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        Arrays.sort(weights);
        
        for(int i=0;i<weights.length-1;i++) {
            for(int j=i+1;j<weights.length;j++) {
                if(weights[i] * 2 < weights[j]) break;
                if(weights[i] == weights[j]) answer++;
                if(weights[i] * 3 == weights[j] * 2) answer++;
                if(weights[i] * 4 == weights[j] * 2) answer++;
                if(weights[i] * 4 == weights[j] * 3) answer++;
            }
        }
        return answer;
    }
}

 

 

 

 

따라서 반복문 하나로도 해결 가능한 알고리즘이 필요합니다. weights의 원소를 HashMap에 저장해가면서 앞서 살펴본 i) ~ iv) 케이스를 type1 ~ type4로 선언해놓고 HashMap에 type1 ~ type4와 일치하는 key가 있는지 확인하여 있다면 answer을 증가시킵니다. 

 

이때 HashMap을 이용한 이유는, getOrDefault() 메소드를 활용한 중복 원소 관리가 용이하고, 또 하나는 containsKey() 메소드 때문입니다. ArrayList에도 contains()라는 메소드가 존재하기는 하지만 시간 복잡도 면에서 큰 차이가 있습니다. contains()는 O(n)시간이 걸리지만, containsKey()는 O(1) 시간이면 찾고자 하는 원소 포함 여부를 파악할 수 있습니다.

 

 

import java.util.HashMap;
import java.util.Arrays;
class Solution {
    public long solution(int[] weights) {
        long answer = 0;
        Arrays.sort(weights);
        HashMap<Double,Integer> map = new HashMap<>();
        
        for(double weight : weights) {
            double type1 = weight * 1.0;
            double type2 = weight * 0.5;
            double type3 = weight * 2.0 / 3.0;
            double type4 = weight * 0.75;
            
            if(map.containsKey(type1)) answer += map.get(type1);
            if(map.containsKey(type2)) answer += map.get(type2);
            if(map.containsKey(type3)) answer += map.get(type3);
            if(map.containsKey(type4)) answer += map.get(type4);
            
            map.put(weight, map.getOrDefault(weight,0)+1);
        }
        return answer;
    }
}

 

 

처음보다 더 빠른 시간에 해결 가능한 것을 살펴볼 수 있습니다.