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

코딩테스트 연습 - 시소 짝꿍 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    map<int, long long> mp; //m.second * (m.second - 1) / 2이 int범위 넘을 수 있으므로 second 값은 long long
    for(int i = 0; i < weights.size(); i++)
        mp[weights[i]]++;
    for (auto m:mp)
        if(m.second >= 2)
            answer += m.second * (m.second - 1) / 2;//같은 값이 나오는 경우를 우선 더해줌
    sort(weights.begin(), weights.end());
    weights.erase(unique(weights.begin(), weights.end()), weights.end());//중복 제거
    int pivot = 0;
    for(int i = 1; i < weights.size(); i++)
    {
        for(int j = pivot; j < i; j++)
        {
            if(weights[i] * 2 == weights[j] * 4 
               || weights[i] * 2 == weights[j] * 3 
               || weights[i] * 3 == weights[j] * 4)
            {
                answer += mp[weights[i]] * mp[weights[j]];
            }
        }
        while(weights[pivot] * 4 < weights[i] * 2)
            pivot++;
    }
    return answer;
}

풀이 방법

우선 키포인트는

케이스는 무조건 4가지라는 것이다

(100, 100) => 같은 값

(100, 200) => 작은 값 * 4 = 큰 값 * 2

(200, 300) => 작은 값 * 3 = 큰 값 * 2

(300, 400) => 작은 값 * 4 = 큰 값 * 3

 

일단 이것을 머리속에 넣어두고

같은 값끼리 짝꿍이 될 경우를 우선적으로 더해주었다.

 

mp에 나온 값만큼 넣어주고 이 값이 2 이상이면 (n) * (n - 1) / 2로 나올 수 있는 조합의 경우의 수 (nC2)를 더해주었다.

이 과정을 거치고 나면

sort(weights.begin(), weights.end());

weights.erase(unique(weights.begin(), weights.end()), weights.end()); 로 중복을 제거해준다.

문장의 의미 :unique(weights.begin(), weights.end()) => weight의 처음부터 끝까지 중 unique하지 않은 것들은 맨 뒤로 보내버림

unique(weights.begin(), weights.end())의 값은 쓰레기값의 첫번째 인덱스가 오게 됨

weights.erase(unique(weights.begin(), weights.end()), weights.end()); => 쓰레기값의 첫번째 인덱스부터 마지막 인덱스까지를 삭제한다.

 

그 다음에 이중 for문 비스무리한것을 돌려주면서 pivot을 오른쪽으로 옮겨주어 시간복잡도를 줄이려 했음

앞서 말했듯 , 무게가 같은 경우를 제외하면 올 수 있는 경우의 수는 3가지이므로

index 1부터 시작해서 그보다 앞에있는 값과 현재 값의 관계가 3가지 경우의 수에 해당되면 

우리가 map에서 이미 각 숫자들이 몇 개 있는지 알아냈으므로 그만큼 더해줌. 그것이 조합의 합이 됨.

 

만약, pivot의 위치에서 가장 크게 4를 곱한것보다 현재 위치에서 2를 곱한 값이 더 크면 그 왼쪽은 더이상 참조하지 않아도 되므로 pivot을 증가시킨다.