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

 

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

 

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

프로그래머스

---

 

해결전략

 

조합(Combination)과 해시맵(Hash Map)

'조합'이란 n개의 원소 중에서 r개를 순서 없이 선택하는 것을 의미한다. 이 코드에서는 동일한 몸무게를 가진 사람들의 쌍을 찾기 위해 조합을 사용한다.

 '해시맵'이라는 데이터 구조를 사용했다. 해시맵은 키와 값을 한 쌍으로 저장하는 데이터 구조로, 여기서는 몸무게를 Key로, 그 몸무게를 가진 사람의 수를 Value로 사용했다. 이를 통해 특정 몸무게를 가진 사람이 몇 명인지 빠르게 알아낼 수 있다.

따라서 이 문제는 몸무게에 따른 사람의 수를 해시맵에 저장하고, 이를 바탕으로 특정 관계를 가진 사람들의 쌍을 조합으로 찾아내는 문제라고 할 수 있다. 

---

 

정답 코드

 

#include <vector>
#include <algorithm>
using namespace std;

vector<long long> ppl(1001);

long long solution(vector<int> weights) {
    
    for (int i = 0; i < weights.size(); i++) 
        ppl[weights[i]]++; // 각 몸무게에 대한 사람 수를 증가시킴

    long long answer = 0;
    for (int i = 0; i < weights.size(); i++)
    {   
        // 1 : 2 (=2:4)
        long long value = weights[i] * 2;
        if (value <= 1000)
            answer += ppl[value]; // 현재 몸무게의 2배인 사람의 수를 더함

        // 2 : 3
        if (weights[i] % 2 == 0) {
            long long value = (weights[i] / 2) * 3;
            if (value <= 1000)
                answer += ppl[value]; // 현재 몸무게의 3/2배인 사람의 수를 더함
        }
        // 3 : 4
        if (weights[i] % 3 == 0) {
            long long value = (weights[i] / 3) * 4;
            if (value <= 1000)
                answer += ppl[value]; // 현재 몸무게의 4/3배인 사람의 수를 더함
        }
    }

    // 몸무게가 같은 경우
    for (int i = 100; i <= 1000; i++) 
    {
        if (ppl[i] >= 2) // 몸무게가 같은 사람이 2명 이상일 때
        {
            answer += ppl[i] * (ppl[i] - 1) / 2; // 조합 공식 nC2인 n*(n-1)/2를 이용해 쌍의 수를 구함
        }
    }

    return answer;
}

 

---

 

 

unorder_map 자료형을 사용한 풀이

 

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

long long solution(vector<int> weights) {
    unordered_map<int, long long> weight_map; // 몸무게를 key로, 해당 몸무게를 가진 사람들의 수를 value로 하는 unordered_map 생성

    for (auto weight : weights) 
        weight_map[weight]++; // 각 몸무게에 대한 사람 수를 증가

    long long answer = 0;

    for (auto weight : weights)
    {
    	// 1:2 (=2:4)
        long long value = weight * 2;
        if (weight_map.count(value)) 
            answer += weight_map[value];
		
        // 2:3 
        if (weight % 2 == 0) {
            value = (weight / 2) * 3; 
            if (weight_map.count(value))
                answer += weight_map[value];
        }
        // 3:4 관계 체크
        if (weight % 3 == 0) {
            value = (weight / 3) * 4;
            if (weight_map.count(value))
                answer += weight_map[value];
        }
    }

    for (auto it : weight_map) 
    {
        if (it.second >= 2) 
            answer += it.second * (it.second - 1) / 2; // 몸무게가 같은 경우, 조합 공식 nC2를 이용해 쌍의 수를 구함
    }

    return answer;
}

 

 

---