[프로그래머스]level.2 - 시소 짝꿍(C++)

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

프로그래머스

내 풀이

1. 이중 for문

시간 초과는 안나지만 실행시간이 오래 걸린다.

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

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    
    // 오름차순 정렬
    sort(weights.begin(), weights.end());
    
    int same_count = 0;
    
    for(int i = 0; i < weights.size()-1; ++i)
    {
        int left = weights[i];
        
        for(int j = i+1; j < weights.size(); ++j)
        {
            int right = weights[j];
            
            if( left == right
               || left*2 == right
               || left*3 == right*2
               || left*4 == right*3)
            {
                ++answer;
            }
        }
        
    }
    
    return answer;
}

2. map

map의 key와 value 를 long long 타입으로 해줘야 한다.

#include <string>
#include <vector>
#include <map>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    map<long long, long long> weight_map;
    
    for(const auto& w : weights)
    {
        ++weight_map[w];
    }
    
    for(const auto& w : weight_map)
    {
        answer += (w.second * (w.second-1))/2;
        
        if(weight_map.end() != weight_map.find(w.first * 2))
            answer += weight_map[w.first * 2] * w.second;
        
        if(0 == w.first % 2 && weight_map.end() != weight_map.find(w.first / 2 * 3))
            answer += weight_map[w.first / 2 * 3] * w.second;
        
        if(0 == w.first % 3 && weight_map.end() != weight_map.find(w.first / 3 * 4))
            answer += weight_map[w.first  / 3 * 4] * w.second;
            
    } 
    
    return answer;
}