[알고리즘/C++] 프로그래머스 - 시소 짝꿍 (Lv.2)

✏️ 풀이 과정
1. 단순 이중 for문으로 시도했더니 시간초과로 실패
2. 동일한 몸무게는 nC₂ 공식을 사용하여 처리하면 되므로 제거
(👉 이렇게만 해도 시간 초과는 나지 않았다)
3. map에 [몸무게, 개수] 형태로 저장해서 관리
4. 최대공약수, 최소공배수를 사용했었는데 자꾸만 예상했던 것보다 코드가 복잡해져서 다른 방법 시도
5. 결국 시소 양쪽 무게에 각각 2, 3, 4를 곱한 값들 중 일치하는 값이 있다면 짝꿍!
(👉 위 개념을 최소공배수로 이해했었는데 그렇게 처리했더니 통과가 되지 않았다.
2, 3, 4배수 중에 최소공배수가 포함되지 않는 경우가 있어서 그런듯 싶다)
6. 단순하게 set에 집어넣고 개수가 6개보다 작으면 (= 중복되는 값이 있으면 = 일치하는 값이 있으면) answer 값을 더했다.

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <map>

using namespace std;

long long solution(vector<int> weights)
{
    long long answer = 0;

    sort(weights.begin(), weights.end());

    map<int, long long> mWeights;
    for (int i = 0; i < weights.size(); ++i)
    {
        mWeights[weights[i]]++;
    }
    weights.erase(unique(weights.begin(), weights.end()), weights.end());

    set<long long> iset;
    for (int i = 0; i < weights.size() - 1; ++i)
    {
        for (int j = i + 1; j < weights.size(); ++j)
        {
            iset.clear();
            iset.insert(weights[i] * 2);
            iset.insert(weights[i] * 3);
            iset.insert(weights[i] * 4);
            iset.insert(weights[j] * 2);
            iset.insert(weights[j] * 3);
            iset.insert(weights[j] * 4);

            if (iset.size() < 6)
            {
                answer += mWeights[weights[i]] * mWeights[weights[j]];
            }
        }
    }

    for (auto weight : mWeights)
    {
        if (weight.second >= 2)
            answer += (weight.second * (weight.second - 1)) / 2;
    }

    return answer;
}

✏️ 다른 풀이