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

프로그래머스

 

📄 문제

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

 

📝 풀이

#include <string>
#include <vector>
#include <map>

using namespace std;

long long solution(vector<int> weights) {
	map<long long, long long> m;

	for (long long n : weights)
		++m[n];

	long long answer = 0;
	for (pair<long long, long long> p : m)
	{
		long long w = p.first; // weight
		long long c = p.second; // count

		// 같은 몸무게의 인원수가 1명 초과라면 서로 짝이 될 수 있음
		if (c > 1)
			answer += (c * (c - 1) / 2); // 간선의 개수 계산식

		// 정확히 나누어 떨어질 때 계산해야함 (나누어 떨어지지 않으면, 대칭될 수 없음)
		if (w * 3 % 2 == 0)
			if (m.find(w * 3 / 2) != m.end()) // 3 : 2 지점 (1:1.5)
				answer += (m[w * 3 / 2] * c);

		if (w * 4 % 2 == 0)
			if (m.find(w * 4 / 2) != m.end()) // 4 : 2 지점 (1:2)
				answer += (m[w * 4 / 2] * c);

		if (w * 4 % 3 == 0)
			if (m.find(w * 4 / 3) != m.end()) // 4 : 3 지점 (1:1.33f)
				answer += (m[w * 4 / 3] * c);
	}

	return answer;
}

• map을 이용하여 문제를 해결하였습니다.
• 중복되는 weights의 개수를 map에 삽입하여 계산합니다.
• 같은 몸무게가 여려명있다면, 서로 연결지을 수 있기에 노드의 개수 공식을 이용하여 계산합니다.
• 각각 2(m), 3(m), 4(m)에서 가능하기에 1:1.5, 1:2, 1:1.33f 거리에서 같은 몸무게가 m에 있다면, 해당 인원수와 현재 선택된 인원수 c를 곱하여 정답을 누적해나갑니다.