[프로그래머스][C++] 시소 짝꿍

시소 짝꿍

문제 링크

시소 짝꿍

분석

시소의 균형을 이루기 위해 두 사람이 타는 좌우의 거리와 몸무게의 곱이 같아지는 값을 구해야합니다.
결과적으로 시소 짝꿍이 될 수 있는 경우의 수를 세는 문제입니다.

같은 몸무게인 사람들끼리는 1:1 비율이므로 항상 시소 짝꿍이 가능합니다.
서로 다른 몸무게라면, 비율이 2:3, 1:2, 3:4 중 하나가 되어야합니다.

조합할 수 있는 모든 쌍을 순회할 필요 없이 몸무게 등장 횟수를 활용하면 시간 복잡도를 줄일 수 있습니다.

A의 몸무게가 Weight1, B의 몸무게가 Weight2이며, 각각 거리가 Distance1, Distance2만큼 떨어져 있다면 다음과 같습니다.
Weight1 * Distance1 == Weight2 * Distance2 혹은 Weight1 / Weight2 == Distance1 / Distance2

풀이

#include <vector>
#include <unordered_map>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    
    // 각 몸무게가 몇 번 등장했는지를 저장하는 해시맵
    unordered_map<int, int> weightCount;
    
    for (int weight : weights)
    {
        ++weightCount[weight];
    }
    
    // 같은 몸무게끼리 짝을 이루는 경우 (1:1 비율)
    for (const auto& [weight, count] : weightCount)
    {
        if (count > 1)
        {
            // 짝 개수를 구하고 더한다.
            // 오버플로우 방지를 위해 long long으로 형변환
            answer += (static_cast<long long>(count) * static_cast<long long>(count - 1)) / 2;
        }
    }
    
    // 서로 다른 몸무게끼리 짝을 이루는 경우
    for (const auto& [weight, count] : weightCount)
    {
        // 거리 비율
        vector<pair<int, int>> ratios = {{2, 3}, {3, 4}, {1, 2}}; 
        
        // 현재 몸무게를 각 비율별로 계산해본다.
        // A × 거리 = B × 거리 일때, B = (A * a) / b
        for (const auto& ratio : ratios)
        {
            // 현재 몸무게에 비율의 분자를 곱한 값 (A * a)
            // 오버플로우 방지를 위해 long long으로 형변환
            long long num = static_cast<long long>(weight) * static_cast<long long>(ratio.first);

            // 현재 비율로 나눴을 때 결과값이 정수인 경우
            if (num % ratio.second == 0)
            {
                // B = (A * a) / b
                int target = num / ratio.second;

                // 짝꿍이 될 수 있는 몸무게가 있는지 찾는다.
                if (weightCount.find(target) != weightCount.end())
                {
                    // 짝 개수를 구하고 더한다.
                    answer += weightCount[target] * count;
                }
            }
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• 각 몸무게가 몇 번 등장했는지를 저장하는 반복문 $O(n)$
• 같은 몸무게끼리 짝을 이루는 경우를 계산하는 반복문 $O(m)$
  • m은 서로 다른 몸무게의 개수
• 서로 다른 몸무게끼리 짝을 이루는 경우를 계산하는 반복문 $O(m \times 3)$
• $O(n) + O(m) + O(m \times 3)$

공간 복잡도는 $O(m)$입니다.

• 각 몸무게가 몇 번 등장했는지를 저장하는 해시맵 unordered_map<int, int> weightCount $O(m)$

테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.01ms, 4.22MB)
테스트 3 〉 통과 (0.02ms, 4.22MB)
테스트 4 〉 통과 (0.46ms, 4.21MB)
테스트 5 〉 통과 (0.38ms, 4.27MB)
테스트 6 〉 통과 (0.53ms, 4.55MB)
테스트 7 〉 통과 (0.61ms, 4.75MB)
테스트 8 〉 통과 (0.72ms, 5.12MB)
테스트 9 〉 통과 (0.94ms, 5.76MB)
테스트 10 〉 통과 (1.85ms, 6.57MB)
테스트 11 〉 통과 (1.21ms, 6.43MB)
테스트 12 〉 통과 (1.19ms, 6.44MB)
테스트 13 〉 통과 (2.19ms, 6.57MB)
테스트 14 〉 통과 (0.98ms, 6.54MB)
테스트 15 〉 통과 (2.70ms, 6.43MB)
테스트 16 〉 통과 (0.01ms, 3.68MB)
테스트 17 〉 통과 (0.01ms, 4.14MB)