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

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

프로그래머스

풀이

완전 탐색을 사용하는 풀이와, map,set을 사용한 풀이가 있다. 

1. weight 범위가 100,000 이라 O(N^2)이면 시간 초과가 날 것으로 생각했는데 테스트 케이스 중에 그런 것이 없나 보다. 다른 분들 코드를 봤는데 완전 탐색으로도 통과되었다..

//완전탐색

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(vector<int> weights) {
    sort(weights.begin(), weights.end());
    long long answer = 0;
    for(int i = 0; i < weights.size(); i++)
        for(int j = i + 1; j < weights.size(); j++)
        {
            if(weights[i] == weights[j]) answer++;
            else if(weights[i] * 4 == weights[j] * 3) answer++;
            else if(weights[i] * 4 == weights[j] * 2) answer++;
            else if(weights[i] * 3 == weights[j] * 2) answer++;
        }
    return answer;
}

1. Map, set 코드
   1. 무게 벡터를 중복 없이 저장하기 위한 set과, 중복된 값이 몇 개인지 카운트 하는 map 자료 구조를 사용한다.
   2. set 에 대해 반복문을 돌면서 먼저 중복 카운트 값의 nC2 조합을 계산해준다. 만약, 100이 3개라면 중복 없이 2개를 선택하면 3C2 = 3(2)/2 이다.
   3. 상대방으로 가능한 무게를 검사해야 한다. 이때, B=A*2/3, 2/4, 3/2, 3/4, 4/2, 4/3 이 가능한데, B=A*2/3 와 A=B*3/2와 같이 중복된 계산을 방지하기 위해 2/3, 2/4, 3/4 에 대해서만 검사한다.
   4. 현재 무게의 개수 wSize와 검사해야 하는 무게의 개수 num 조합을 계산한다. (answer += wSize*num)

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

using namespace std;

int r[3]={2, 1, 3};
int d[3]={3, 2, 4};

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

    set<int> w;
    map<int, int> wc;

    for (auto& i:weights){
        w.insert(i);
        wc[i]++;
    }

    for (auto& weight : w){
        long long wSize=wc[weight];
        answer += wSize*(wSize-1)/2;

        for (int i=0; i<3; i++){
            if (weight*r[i]%d[i]) continue;

            int calc = weight*r[i]/d[i];
            // cout << weight << " " << calc << endl;
            long long num = wc[calc];
            answer += wSize * num;
        }
    }
    return answer;
}