☆ [2] 시소 짝꿍 (조합, 이중 순회)

문제 설명
어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다.
이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토크의 크기가 서로 상쇄되어 완전한 균형을 이룰 수 있다면 그 두 사람을 시소 짝꿍이라고 합니다. 즉, 탑승한 사람의 무게와 시소 축과 좌석 간의 거리의 곱이 양쪽 다 같다면 시소 짝꿍이라고 할 수 있습니다.
사람들의 몸무게 목록 weights이 주어질 때, 시소 짝꿍이 몇 쌍 존재하는지 구하여 return 하도록 solution 함수를 완성해주세요.

제한 사항
2 ≤ weights의 길이 ≤ 100,000
100 ≤ weights[i] ≤ 1,000
몸무게 단위는 N(뉴턴)으로 주어집니다.
몸무게는 모두 정수입니다.

입출력 예
weights result
[100,180,360,100,270] 4
입출력 예 설명
{100, 100} 은 서로 같은 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 360} 은 각각 4(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{180, 270} 은 각각 3(m), 2(m) 거리에 마주보고 앉으면 균형을 이룹니다.
{270, 360} 은 각각 4(m), 3(m) 거리에 마주보고 앉으면 균형을 이룹니다.

---

오답 노트

간단한 조합 문제인줄 알았는데, 함정 투성인 문제였다.

순열의 조합 식도 필요하고,

이중포문을 줄여야하는 방법도 생각해야 한다.

1. 먼저 중복되는 무게의 개수를 무게별로 map에 저장

2. 각 map의 개수가 서로 짝지어질 수 있는 조합의 수를 구한다.

ㄴ (동일한 n 개중 2개를 뽑는 경우의 수) 를 생각하면 된다.

3. 해당 map을 순회하면서 각 무게가 서로 짝꿍인지 판별한다.

ㄴ 이때 짝꿍이 된다면, 무게A 의 개수 x 무게B의 개수 를 해주어야 해당 무게가 짝지어지는 조합의 개수를 구할 수 있다.

* 개수를 구할 떄 long long 형으로 변환해서 answer에 넣어야 한다.

ㄴ 최대 개수가 int 형을 넘을 수 있기 때문이다.

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

using namespace std;

bool IsPair(int weightA, int weightB)
{
	if (weightA * 2 == weightB * 3
		|| weightA * 2 == weightB * 4
		|| weightA * 3 == weightB * 4
		|| weightB * 2 == weightA * 3
		|| weightB * 2 == weightA * 4
		|| weightB * 3 == weightA * 4)
		return true;

	return false;
}

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

	map<long, long long> m;
	for (int i = 0; i < weights.size(); i++)
		m[weights[i]] += 1;

	vector<int> vec;
	for (auto& pair : m)
	{
		long long count = pair.second;
		if (count > 1)
			answer += ((count * (count - 1)) / 2); // 조합 계산 추가
		vec.push_back(pair.first);
	}

	for (int i = 0; i < vec.size() - 1; i++)
	{
		int weight = vec[i];
		for (int j = i + 1; j < vec.size(); j++)
		{
			if (IsPair(weight, vec[j]))
				answer += (long)(long)(m[weight] * m[vec[j]]);
		}
	}

	return answer;
}