시소 짝꿍(해결)

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

구현 아이디어 7분 구현 23분

풀이(76.5점)

테스트 케이스 12번~15번을 실패했다. 어떤 반례가 있는지 찾아서 다시 풀어 볼 문제.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 최대 무게 1000. 검사는 1000보다 큰 인덱스까지 이루어진다.
int check[10001];

long long solution(vector<int> weights) {
    long long answer = 0;
    
    sort(weights.begin(), weights.end());
    int N = weights.size();
    
    for(int i = 0; i < N; ++i)
        check[weights[i]]++;
    
    for(int i = 0; i < N; ++i)
    {
        int cur_weight = weights[i];
        
        // 현재 무게가 cur_weight라면 짝꿍이 될 수 있는 경우의 수는 총 4가지가 있다.
        // 1. 같은 무게
        answer += (check[cur_weight] * (check[cur_weight] - 1)) / 2;
        check[cur_weight] = 0;
        
        // 2. 무게 2배.
        answer += check[cur_weight * 2];
        
        // 3. 무게 3/2배.
        if(cur_weight % 2 == 0)
            answer += check[cur_weight / 2 * 3];
        
        // 4. 무게 4/3배.
        if(cur_weight % 3 == 0)
            answer += check[cur_weight / 3 * 4];
    }
    
    return answer;
}

---

풀이

형변환이 문제였다. check 배열을 long long으로 두니 통과했다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 최대 무게 1000. 검사는 1000보다 큰 인덱스까지 이루어진다.
long long check[10001];

long long solution(vector<int> weights) {
    long long answer = 0;
    
    sort(weights.begin(), weights.end());
    int N = weights.size();
    
    for(int i = 0; i < N; ++i)
        check[weights[i]]++;
    
    for(int i = 0; i < N; ++i)
    {
        int cur_weight = weights[i];
        
        // 현재 무게가 cur_weight라면 짝꿍이 될 수 있는 경우의 수는 총 4가지가 있다.
        // 1. 같은 무게
        answer += (check[cur_weight] * (check[cur_weight] - 1)) / 2;
        check[cur_weight] = 0;
        
        // 2. 무게 2배.
        answer += check[cur_weight * 2];
        
        // 3. 무게 3/2배.
        if(cur_weight % 2 == 0)
            answer += check[cur_weight / 2 * 3];
        
        // 4. 무게 4/3배.
        if(cur_weight % 3 == 0)
            answer += check[cur_weight / 3 * 4];
    }
    
    return answer;
}

---

여담. 습관적으로 sort을 했는데 하고 나서 왜 sort을 한 결과와 하지 않은 결과가 다른지 이해가 안돼서 비주얼 스튜디오에서 디버깅을 했다.
위 로직에서 자신보다 크거나 같은 무게가 몇 명이나 존재하는지 체크하는데, check[cur_weight] = 0; 여기서 자신을 0명으로 바꾸기 때문에 정렬을 해야한다.
예: 360이 먼저 나와서 check[360]이 0이 되었는데 이후에 270을 검사하면 360이 0이기 때문에 answer에 더해지지 않는다.