시소 짝궁

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

프로그래머스

 

문제 설명

 

어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 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) 거리에 마주보고 앉으면 균형을 이룹니다.

 

문제 솔루션

카운팅

1. Map 을 활용하여 모든 몸무게에 대해서 각 몸무게 별로 몇명이 존재하는지 계산

2. 각 사람들에 대해서 2배, 4/3배, 3/2배의 수를 합산

3. 같은 무게를 가진 사람수를 K 라고 했을 때, K Combination 2 만큼 합산

 

시간복잡도

O(W)

트러블 슈팅

1. 타입

만약, 최대 인원수 10만명이 다 동일한 무게라고 했을 때, 10만 Combination 2 는 몇일까? 약, 50억정도 된다. 즉, 타입이 Long 이어야 한다. 따라서 값을 더해줄때, `long` 으로 캐스팅이 필요하다.

 

2. Int / Int = Int 에서 발생하는 문제

조건처리해야한다.

 

2. 알고리즘..?

트러블슈팅이라기 보단, 멍청비용이라고 할까나, 처음 K 가 존재하는 개수를 구할 때, 이분 탐색으로 구했었는데, Counting 으로 충분히 된다는 것을 늦게 알았다.

변경 전 코드

Map<Integer, Integer> counts = new HashMap<>(weights.length);
for (int wei: weights) {
	counts.merge(wei, 1, Integer::sum);
}

Arrays.sort(weights);

for (int i = 0; i < weights.length; i++) {
    int wei = weights[i];
    // 4/3 배, 3/2배, 4/2배
    // upper(K) : k보다 큰 정수가 처음 나오는 위치
    // lower(K) : k이상이 처음 나오는 위치
    // K 의 개수는 upper - lower : O(logN)
    pairs += upper(weights, i + 1, wei * 2) - lower(weights, i + 1, wei * 2);
    ...
}

 

변경 후 코드

Map<Integer, Integer> counts = new HashMap<>(weights.length);
for (int wei: weights) {
	counts.merge(wei, 1, Integer::sum);
}


long pairs = 0;
for (int i = 0; i < weights.length; i++) {
    int wei = weights[i];
    // 4/3 배, 3/2배, 4/2배
    pairs += counts.getOrDefault(wei * 2, 0);
	...
}

 

전체 코드 

import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
import java.util.Map.Entry;

class Solution {
    
    public long solution(int[] weights) {
        Map<Integer, Integer> counts = new HashMap<>(weights.length);
        for (int wei: weights) {
            counts.merge(wei, 1, Integer::sum);
        }
        
        long pairs = 0;
        for (int i = 0; i < weights.length; i++) {
            int wei = weights[i];
            // 4/3 배, 3/2배, 4/2배
            pairs += counts.getOrDefault(wei * 2, 0);
            if (wei % 3 == 0) {
                pairs += counts.getOrDefault(wei * 4 / 3, 0);
            } 
            if (wei % 2 == 0) {
                pairs += counts.getOrDefault(wei * 3 / 2, 0);
            }
        }
        
        for (Entry<Integer, Integer> entry: counts.entrySet()) {
            pairs += (long) entry.getValue() * (entry.getValue() - 1) / 2;
        }
        
        return pairs;
    }
}