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

이 문제는 비례식을 이용해서 푸는 문제이다.

 

이 문제에서 핵심은 map을 사용하거나, vector를 사용해서 해당 비례식에 맞는 몸무게를 한번에 찾아내는 것이다.

 

첫번째로 1 : 1, 1 : 2, 2 : 3, 3 : 4 로 비례식이 좁혀진다는 것을 발견해야한다. 시소가 2m, 3m, 4m 씩 자리가 양 쪽에 있기 때문에, 나올 수 있는  경우의 수는 2:2, 2:3, 2:4, 3:2, 3:3, 3:4, 4:2, 4:3, 4:4 가 된다. 약분을 하고 중복된 가지수를 제거하면 1:1, 1:2, 2:1, 2:3, 3:2, 3:4, 4:3 이 나오는데, 순서만 바뀐 것도 제거해주면 최종적으로 1:1, 1:2, 2:3, 3:4 가 나온다.

 

두번째로 몸무게에 대해 개수를 세고, 몸무게에 대해 루프를 돌면서 상대방의 몸무게를 계산하고, 이를 찾으면서 가지수에 더해나가면 된다. 몸무게가 같은 경우를 따로 뺀 이유는 루프를 돌면서 순서만 바뀐 쌍이 같이 더해지기 때문이다.

 

처음에는 map을 이용해서 풀으려고 했으나, 너무 복잡해지고 답이 제대로 나오지 않아 검색을 해봤다. 풀이가 거의 비슷했으나 vector를 이용한 아주 쉬운 풀이가 있었다. 몸무게가 [100, 1000] 이라는 사실을 제대로 읽었다면 굳이 맵을 쓰지 않았을 것이라는 아쉬움이 있었다.

 

또한 구현을 마친 뒤에도 오답이 계속 나왔는데, 이는 매개변수로 받는 number가 int로 선언이 되어있었기 때문이었다. long long 을 사용하는 문제에는 그냥 모든 자료형을 long long으로 맞추는 게 현명한 것 같다.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

/*
    1 : 2
    2 : 3
    3 : 4
*/

#define WEIGHT_MAX 1000

typedef long long ll;

ll calculateCombination(ll number) {
    return (ll)(number * (number - 1)) / 2;
}

ll countSame(vector<ll> weightCounts) {
    ll result = 0;
    
    for (int i = 100; i <= 1000; i++) {
        if (weightCounts[i] >= 2) {
            result += calculateCombination(weightCounts[i]);
        }
    }
    
    return result;
}

vector<ll> makeWeightCounts(vector<int> weights) {
    vector<ll> results(WEIGHT_MAX + 1, 0);
    
    for (int weight : weights) {
        results[weight]++;
    }
    
    return results;
}

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

    for (int weight : weights) {
        if (weight % 2 == 0) {
            ll oppoWeight = (weight / 2) * 3;
            
            if (oppoWeight <= 1000) {
                answer += weightCounts[oppoWeight];
            }
        }
        
        if (weight % 3 == 0) {
            ll oppoWeight = (weight / 3) * 4;
            
            if (oppoWeight <= 1000) {
                answer += weightCounts[oppoWeight];
            }
        }
        
        ll oppoWeight = weight * 2;
        if (oppoWeight <= 1000) {
            answer += weightCounts[oppoWeight];
        }
    }
    
    answer += countSame(weightCounts);
    
    return answer;
}