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

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

프로그래머스

 

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

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

    unordered_map<int, int>um;
    for (int i = 0; i < weights.size(); i++)
        um[weights[i]]++;

    for (pair<int, int> item : um)
    {
        int key = item.first;
        if (um[key] >= 2)
            answer+=((long long)item.second*(item.second-1)/2);
        
        if(key*2%1==0&&um.find(key*2) != um.end())
            answer+=(long long)um[key]*um[key*2];
        if(key*3%2==0&&um.find(key*3/2)!=um.end())
            answer+=(long long)um[key]*um[key*3/2];
        if(key*4%3==0&&um.find(key*4/3)!=um.end())
            answer+=(long long)um[key]*um[key*4/3];
    }
    return answer;
}

 

이 문제는 시소 짝꿍이 되는 경우의 수를 구하는 문제이다. 

시소 짝꿍은 어느자리에 앉든 평형을 이룰수 있다면 짝꿍이다. 

각 자리는 2,3,4미터 중심에서 떨어져 있다. 즉 몸무게의 비율은 1:1, 1:2, 2:3, 3:4 의 경우의 수가 있다.

 

이를 unordered_map을 통해서 구현하였다. 

key를 통해 값을 찾기 때문에 탐색에 대한 시간이 O(1)이며 키에 대해서 수를 카운트도 할 수 있기 때문이다. 

 

 int key = item.first;
        if (um[key] >= 2)
            answer+=((long long)item.second*(item.second-1)/2);

먼저 for문을 돌며 1:1의 경우를 체크하는 코드이다. 

같은 몸무게가 두 명 이상일 경우 nC2 만큼 센다. 왜냐하면 weights의 각 몸무게는 각 사람을 나타내기 때문이다. 

같은 몸무게의 여러사람 중 두 명을 고르는 경우의 수를 계산한 것이다. 

 

if(key*2%1==0&&um.find(key*2) != um.end())
            answer+=(long long)um[key]*um[key*2];
        if(key*3%2==0&&um.find(key*3/2)!=um.end())
            answer+=(long long)um[key]*um[key*3/2];
        if(key*4%3==0&&um.find(key*4/3)!=um.end())
            answer+=(long long)um[key]*um[key*4/3];

그리고 각각 1:2, 2:3, 3:4 의 비율을 체크하는 경우이다. 

먼저 비율에 대한 계산을 하여 얻는 키가 유효한지 체크한다. 키는 정수형이기 때문에 key가 5가 된다면 5*3/2는 7.5라 유효하지 않게 되기 때문이다. 

그 후, 맵에서 찾아 있다면 key C 1 * (비율계산한 키값) C 1 만큼 센다. 

마찬가지로 여러 사람 중 한명을 선택하는 경우의 수이기 때문이다. 

 

answer에 더할 때 곱연산에서 반드시 long long으로 형변환을 해야한다. 최대 십만의 길이를 가지는 weights 에서 카운트가 4만이 넘어가는 두 수가 곱해지면 int형의 범위를 넘기기 때문이다. 

 

이렇게 for문을 돌고 리턴하면 된다.