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

문제

 

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

프로그래머스

 

 

문제풀이

 

앉을 수 있는 경우의 수는 중심으로부터 (2m, 3m), (2m, 4m), (3m, 4m) 이렇게 세 가지가 있다.

따라서 idx번째 무게의 2/3, 1/2, 3/4의 무게를 찾으면 된다.

개수가 int형의 범위를 넘어가므로 map을 선언할 때 int, long long형으로 선언한다.

 

먼저 무게를 빠르게 찾기 위해 unordered_map에 모든 몸무게를 입력한다.

무게가 같은 사람이 여러 명 있을 수 있으므로, nC2의 개수를 구한다.

 

주어진 무게 벡터를 탐색하면서 해당 무게의 2/3, 1/2, 3/4가 되는 값이 있으면 answer에 개수를 더한다.

 

 

코드

#include <vector>
#include <unordered_map>
#define ll long long
using namespace std;

long long solution(vector<int> input) {
    long long answer(0);
    unordered_map<int, ll>weights;

    for (int idx = 0; idx < input.size(); ++idx)
        ++weights[input[idx]];

    for (auto iter = weights.begin(); iter != weights.end(); ++iter) {
        if (iter->second > 1)
            answer += (iter->second) * (iter->second - 1) / 2;
    }

    for (int idx = 0; idx < input.size(); ++idx) {
        if (input[idx] * 2 % 3 == 0)
            answer += weights[input[idx] * 2 / 3];

        if (input[idx] % 2 == 0)
            answer += weights[input[idx] * 1 / 2];

        if (input[idx] * 3 % 4 == 0)
            answer += weights[input[idx] * 3 / 4];
    }

    return answer;
}