[Programmers] 152996번 - 시소 짝꿍 [Java][C++]

문제 링크

---

1. 아이디어

중심으로부터 2m, 3m, 4m 거리의 지점에 좌석이 하나씩 있는 시소에서 시소 짝꿍의 쌍을 구하는 문제로 해시맵을 활용해서 해결했다. weight 목록에서 동일한 몸무게가 주어질 수 있으므로 몸무게를 key, 수를 value로 먼저 전처리해줬다.

시소 짝꿍의 수는 각 몸무게 단위로 계산을 해줬는데 동일한 몸무게의 사람들은 같은 거리에 두면 전부 짝꿍이 되므로 사람의 수를 $N$ 이라 했을 때 $N$ 명 중 $2$ 명을 뽑는 경우의 수인 $\dfrac{N \times (N - 1)}{2}$ 가 된다.

서로 다른 몸무게지만 시소 짝꿍이 되는 경우는 몸무게가 적은 쪽이 한번 세고 큰 쪽이 한번 세게 되므로 몸무게가 작은 쪽을 기준으로만 계산을 해줬다. 먼저 몸무게가 2배 차이가 나서 4m, 2m에 배치하는 경우를 세줬고, 이후 몸무게가 2의 배수이면 3m, 2m에 배치하는 경우의 수를 세줬고, 마지막으로 몸무게가 3의 배수이면 4m, 3m에 배치하는 경우를 세줬다. 처음에 해시맵에 몸무게와 인원수를 저장해줬으므로 해시맵에 반대측 몸무게가 존재하면 인원수를 통해 쌍의 수를 계산할 수 있다.

---

2. 복잡도

시간복잡도	공간복잡도
$O(N)$	$O(N)$

---

3. 코드

풀이 [Java][C++]

계산 과정에서 오버플로우가 발생할 수 있어서 cnt를 long 타입으로 형변환해줬다.

import java.util.*;

class Solution {
    public long solution(int[] weights) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int w : weights) {
            map.put(w, map.getOrDefault(w, 0) + 1);
        }

        long ans = 0;
        for (int w : map.keySet()) {
            long cnt = map.get(w);

            ans += cnt * (cnt - 1) / 2;  // 같은 거리에 위치하는 경우
            ans += cnt * map.getOrDefault(w * 2, 0);  // 4m, 2m에 위치하는 경우
            if (w % 2 == 0) ans += cnt * map.getOrDefault(w * 3 / 2, 0);  // 3m, 2m에 위치하는 경우
            if (w % 3 == 0) ans += cnt * map.getOrDefault(w * 4 / 3, 0);  // 4m, 3m에 위치하는 경우
        }

        return ans;
    }
}

계산 과정에서 오버플로우가 발생할 수 있어서 unordered_map의 value를 long long 타입으로 선언해줬다.

#include <unordered_map>
#include <vector>

using namespace std;

long long solution(vector<int> weights) {
    unordered_map<int, long long> mp;
    for (int w : weights) mp[w]++;

    long long ans = 0;
    for (auto [w, cnt] : mp) {
        ans += cnt * (cnt - 1) / 2;  // 같은 거리에 위치하는 경우

        auto it = mp.find(w * 2);
        if (it != mp.end()) ans += cnt * it->second;  // 4m, 2m에 위치하는 경우

        if (w % 2 == 0) {
            it = mp.find(w * 3 / 2);
            if (it != mp.end()) ans += cnt * it->second;  // 3m, 2m에 위치하는 경우
        }

        if (w % 3 == 0) {
            it = mp.find(w * 4 / 3);
            if (it != mp.end()) ans += cnt * it->second;  // 4m, 3m에 위치하는 경우
        }
    }

    return ans;
}

---