[Algorithm] Programmers :: 시소 짝꿍

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

프로그래머스

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
 
long long solution(vector<int> weights)
{
    long long answer = 0;
 
    sort(weights.begin(), weights.end());
    map<int, long long> m;
 
    for (int i = 0; i < weights.size(); ++i)
    {
        m[weights[i]] += 1;
    }
 
    weights.erase(unique(weights.begin(), weights.end()), weights.end());
 
    for (int i = weights.size() - 1; i >= 0; --i)
    {
        int curWeight = weights[i];
 
        answer += (m[curWeight] * (m[curWeight] - 1)) / 2;
 
        if (curWeight % 3 == 0)
        {
            answer += (m[curWeight * 4 / 3] * m[curWeight]);
        }
 
        if (curWeight % 2 == 0)
        {
            answer += (m[curWeight * 3 / 2] * m[curWeight]);
        }
 
        answer += (m[curWeight * 2] * m[curWeight]);
    }
 
    return answer;
}

 

조건에 맞는 쌍의 개수를 구하는 문제이다.

물론 가장 쉬운방법은 단순완전탐색이지만, weights의 길이는 최대 10만으로, 10만 * 10만의 시간복잡도가 발생하기때문에 고려할 방법은 아니다.

 

다만, 숫자자체는 100 ~ 1000이기 때문에 map을 활용하는 방법으로 코드를 작성했다.

weights를 순회하면서 각 숫자에 대해 카운팅한다.(몇번 나오는지)

그리고 weights에서 중복숫자를 전부 삭제해줬다.

erase와 unique를 사용해서 삭제하면 되는데, unique를 사용하면 중복된 숫자를 벡터 뒷쪽으로 보내버리고 그 시작점을 리턴한다. 그러면 erase를 이용해서 그 시작점부터 end까지 삭제해주면 weights에는 깔끔하게 중복이 제거된 숫자들만 남게된다.

 

그다음 중복이 제거된 weights를 순회하면서, 해당 숫자와 같거나,4/3배,3/2배,2배 인 숫자와의 쌍의 개수를 정답으로 카운팅해준다.

 

같은숫자에 대해서는 nCr을 적용한다. n개에서 2개씩 뽑는것이기 때문에 nC2가 되고, n!에서 (n-r)!만큼 제외한다면 결국 n이랑 n-1만 남기 때문에 (n * n-1) / 2 라는 식이 나온다. 

nCr = n! / r! * (n-r)!

 

이후 다음과 같은 로직을 수행한다.

3으로 나누어 떨어질 경우, 

answer += (m[curWeight * 4 / 3] * m[curWeight]); 을 수행한다.

 

먼저 3으로 나누어 떨어지는것을 검사하는 이유는, 3으로 나누었을 때 나머지가 0, 즉 양의정수를 유지할 수 있는 숫자인지를 검사하는 것이다. (몸무게가 양의정수이여야 하니까)

이후 현재 몸무게의 개수 (m[curWeight])와 현재몸무게의 4/3크기의 몸무게의 개수를 곱해준다.

즉, 이게 뭘 의미하냐면 현재 몸무게로 한쪽에 3m거리에 앉았을 때, 반대쪽에 4m거리에 앉은 경우의 개수를 구하는 것이다.

내가 3m거리에 앉았을때 반대쪽과 수평을 유지하려면 반대쪽 4m앉은사람의 몸무게는 내 몸무게의 4/3이여야 하기 때문이다.

 

이후 코드들도 다 동일하다. 내가 2m 거리에 앉았을 때 반대쪽 3m에 앉는 경우의 개수를 구하기위해 3/2몸무게에 해당하는 개수와 곱해주는 것이다.

 

그다음은 내가 2m, 상대가 4m니까 이경우는 4/2로 그냥 2배몸무게에 해당하는 개수와 곱해주면 된다.

 

(참고로 반복문 순회는 인덱스 i를 0부터시작하든 끝에서부터 시작하든 당연히 상관없다)

 

 

그리고 주의할 점은, 곱의 결과는 int형 범위를 넘기 때문에 반드시 결과값은 long long으로 해줘야한다.

이거 안해준거 때문에 시간을 많이 날렸다..