[lv2] 시소 짝꿍

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

 

수학 문제다.

 

완탐시 최대 O( 3^2 * 10만 * 10만)로 불가능하다.

 

풀이

 

1. 모든 탐색 대신, 모든 원소를 map<key:무게, value:원소의 개수>으로 기록한다.

 

2. 원소의 개수 별로 "가능한 쌍의 수" 값이 담긴 누적 합 배열을 구한다.

e.g.)

원소가 2개 => 쌍의 수 : 1

원소가 3개 => 쌍의 수 : 1 + 2 = 3

원소가 4개 => 쌍의 수 : 1 + 2 + 3 = 6

 

3. 누적 합 배열을 바탕으로 map을 순회하며 answer에 값을 누적한다.

 

4. 중복된 만큼 answer에서 값을 빼준다.

 

e.g.)

[100, 100, 100] // answer : 3, wrong answer : 9

위의 경우, 3번 까지 수행했을 때 출력은 9가 나온다.

 

이는,

100/2 100/2 100/2 => sum[3] = 3

100/3 100/3 100/3 => sum[3] = 3

100/4 100/4 100/4 => sum[3] = 3

 

sum[3] * 3 = 9이기 때문이다.

이미 answer에 이를 누적해놓은 상태이므로, sum[3] * 2를 빼서 중복을 제거한다.

 

---

 

조금 더 자세히 파악하면,

n과 m이 서로 다른 수라면, 각각 /2, /3, /4 한 값은 최대 한 번 겹칠 수 있다.

=> 한 번만 카운트 된다. (문제에서의 요구사항 대로)

 

n과 m이 같은 수라면, /2, /3, /4 한 값은 모두 겹친다.

=> 세 번 카운트 된다.

 

따라서, 같은 수일 경우 두 번의 중복을 빼준다.

(다만, n=1000, m=2000,  /2, /4, /8같이 "2번 이상 연속된 배수"로 나눠야 할 때는 적용할 수 없다.)

import java.util.*;

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

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

        long[] sum = new long[W+1];
        sum[2] = 1;
        for(int i=3; i<=W; i++)
            sum[i] = sum[i-1] + i-1;

        for (int w : weights) {
            map.merge((double) w / 2, 1, (ov, nv) -> ov + 1);
            map.merge((double) w / 3, 1, (ov, nv) -> ov + 1);
            map.merge((double) w / 4, 1, (ov, nv) -> ov + 1);

            dupli.merge(w, 1, (ov, nv) -> ov + 1);
        }

        for(int v : map.values()) {
            if(v == 1)
                continue;

            answer += sum[v];
        }

        for (int v : dupli.values()) {
            if(v == 1)
                continue;

            answer -= sum[v] * 2;
        }

        return answer;
    }
}