C# 시소 짝꿍 - 조합 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/152996

 

 

1차 시도

public long solution(int[] weights) 
{
    long answer = 0;
    var location = new int[3]{ 2, 3, 4 };
    var hash = new HashSet<(int, int)>();

    for(int a = 0; a < weights.Length; ++a)
    {
        for(int b = 0; b < weights.Length; ++b)
        {
            if(a == b) continue;
            if(hash.Contains((a, b))) continue;

            hash.Add((a, b));
            hash.Add((b, a));

            if(IsMatch(location, weights[a], weights[b]))
                ++answer;
        }
    }

    return answer;
}

private bool IsMatch(int[] location, int a, int b)
{
    if(a == b) return true;
    for(int ia = 0; ia < 3; ++ia)
    {
        for(int ib = 0; ib < 3; ++ib)
        {
            if(location[ia] * a == location[ib] * b)
                return true;
        }
    }
    return false;
}

일단 완전 탐색부터 시도.

조합의 중복은 hashSet으로 처리했다.

당연하게도 시간초과.

 

 

2차 시도

public long solution(int[] weights) 
{
    Array.Sort(weights);
    long answer = 0;
    var locA = new int[3]{ 2, 2, 3 };
    var locB = new int[3]{ 3, 4, 4 };

    long sameWeight = 0;
    for(int a = 0; a < weights.Length; ++a)
    {
        for(int b = 0; b < weights.Length; ++b)
        {
            if(a == b) continue;
            if(weights[a] == weights[b])
            {
                ++sameWeight;
                continue;
            }
            if(weights[a] < weights[b])
                continue;

            for(int i = 0; i < locA.Length; ++i)
            {
                if(locA[i] * weights[a] == locB[i] * weights[b])
                {
                    ++answer;
                    break;
                }
            }
        }
    }

    return answer + sameWeight / 2;
}

hashSet을 처리하지않고 정렬로 최대한 예외처리 해서 중복 연산을 수행하지 않도록 처리했다. 

이정도로 최적화를 해도 초과하는 케이스가 있는거 보면 완전탐색으로는 풀기 힘든 문제.

다른 방법을 시도해보자.

 

 

나의 풀이

public long solution(int[] weights) 
{
    long answer = 0;

    // dictionary에 모든 무게를 넣음
    var dict = weights.GroupBy(g => g).ToDictionary(d => d.Key, d => d.Count());
    var matchWeight = new HashSet<int>();
    for(int i = 0; i < weights.Length; ++i)
    {
        // 조합으로 (2, 3), (2, 4), (3, 4)가 나올 수 있다. 거리가 같은경우는 제외
        int cur = weights[i];
        if(cur % 3 == 0)
        {
            if(dict.TryGetValue(cur * 2 / 3, out int value1))
                answer += value1;
        }

        if(cur % 2 == 0)
        {
            if(dict.TryGetValue(cur / 2, out int value2)) // 원래 2 / 4
                answer += value2;

            if(cur % 4 == 0)
            {
                if(dict.TryGetValue(cur * 3 / 4, out int value3))
                    answer += value3;
            }
        }
    }

    // 몸무게가 같은 경우는 그냥 조합 개수 공식으로 구하면 된다. nC2
    long sameWeight = dict.Values.Where(w => w > 1).Sum(s => (long)s * (s - 1) / 2);
    return answer + sameWeight;
}

n * n 복잡도로는 풀기 힘든 문제이니

n을 한번만 순회하기 위해서는 몸무게를 전부 Dictionary로 넣은다음, 

하나씩 순회하면서 분수 곱의 숫자가 몇개나 존재하는지 확인한다.

 

만약 특정 수 k으로 나뉘지 않는다면 k로 나눠도 소수가 나오기 때문에 각 계산을 제외할 수 있다.

특히 2로 나뉘지 않는다면 당연히 4로도 나뉘지 않기 때문에 if문을 중첩할 수 있다.

 

마지막으로 몸무게가 같은 경우는 돌아가면서 서로서로 2명씩 짝 짓는 경우이기 때문에 nC2의 조합으로 풀면 된다. 

완전 탐색으로 풀었을 때와 달리 5번과 6번 케이스의 시간이 극적으로 줄었다.