[프로그래머스] 시소 짝꿍 (c++)

문제 설명

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

---

제한 사항

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

---

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

using namespace std;

long long solution(vector<int> weights) {
	set<long long> keys;
	map<long long, long long> maps;
	long long answer = 0;

	for (size_t i = 0; i < weights.size(); i++)
	{
		maps[weights[i]]++;
		keys.insert(weights[i]);
	}

	for (auto key : keys)
	{
		answer += maps[key] * maps[key * 2];
		if ((float)(key * (3.0 / 2)) - (long long)(key * (3.0 / 2)) < 0.0000001)
			answer += maps[key] * maps[key * (3.0 / 2)];
		if ((float)(key * (4.0 / 3)) - (long long)(key * (4.0 / 3)) < 0.0000001)
			answer += maps[key] * maps[key * (4.0 / 3)];
		answer += (maps[key] * (maps[key] - 1)) / 2;
	}
    return answer;
}

---

문제 유형은 그리디라고 생각되는데 맞는진 모르겠다. 아직 유형 정리는 모르겠다.

 

아이디어.

1. map에 몸무게를 key로  해당 몸무게를 가진 사람의 수를 value에 저장한다.

2. 작은 무게부터 체크해서 짝꿍이 되는 숫자를 가져와 서로 곱한다.

 

작은 수부터 검사를 하므로 2/3, 2/4, 3/4 는 검사하지 않는다.

중간에 if 걸어준 이유는 정수체크를 하기 위함이다. 정수 체크 안하면 의도하지 않은 key 값이 들어가서 오류가 난다.

 

보완점.

1. 더 좋은 정수체크 방법이 있을지(?)는 고민해보자.

2. set 이나 maps의 key 형태는 long long 이 아니라 int로 해도 될 듯 싶다.