프로그래머스 - 숫자 카드 나누기

 

이번 문제는 한쪽만 해당하는 최대 공약수를 찾는 문제로, 배열의 길이와 원소의 크기를 보면 알 수 있듯이, 얼마나 시간 복잡도를 신경 써서 구조를 만드는지가 중심인 문제이다.

 

따라서 먼저 여러가지 방법을 생각해 보았고

 

1. 둘중 한쪽이 가진 카드 중 제일 큰 값부터 1씩 빼가는 역순으로 체크. i==1에서 정지. 의 방식을 for문으로 돌려서 약수를 중심으로 true/false 체킹

이 방식은 브루트 포스 수준의 작업이여서 무조건 시간 초과가 뜰 것 같았다 => 약 5 × 10¹³ 크기의 연산

 

2. 1번 그룹의 모든 정수의 약수들 중 공통된 약수들만 기록 및 중복체킹을 하는 방식으로 하는 게 좋아 보임
+ ex) 0번째 인덱스 의 약수들 >>에서 1 번째 인덱스 >> 2 번째 인덱스 하면서 쭉 이어지며
+이전 인덱스와 공통된 숫자만 남기는 방식 intersectwith(@@) 메서드 사용
+ 마지막에 남은 두 그룹의 약수들 그룹중 겹치지 않는 값 비교는 sysmmetricexceptwith(@@) 메서드 사용

 

이 방식은 매번 약수를 구하는 과정에서 큰 범위의 for문에 접근하게 되기에 필요한 연산이 많다 => 5 ×10⁹

 

 

위 두 가지 방법을 처음 생각 해 보았으나, 제한사항의 범위상 문제는 시간복잡도를 우선적으로 신경 써야 하는 문제 같아 보였기에, 최대한 연산을 덜하게 하는 적은 범위에서의 비교를 하는 것이 맞다고 판단했다.

또한 최대 공약수의 특성상 비교군의 가장 낮은 숫자의 약수가 최대 공약수가 되기 때문에, 가장 낮은 값에 집중하였다.

 

 

 

---

 

 

 

• 먼저 빠른 조회가 가능한, 중복이 없는 HashSet을 사용하여 최대 공약수 담기
•  각 배열의 가장 낮은 값의 약수들의 리스트를 가져와 for 문으로 배열의 전체를 돌며 % 를 통해 나머지가 0이 아닌 => 약수가 아닌 값은 제거하는 방식으로 각각의 최대 공약수를 정리하였고.
• 각각의 최대 공약수를 담은 리스트를 foreach문을 통해 반대편 카드의 배열에 All(x => x)로 확인하여 교차 검증 진행

위와 같은 과정을 거쳐서 문제를 아래와 같이 풀어내었다.

 

 

public int solution(int[] arrayA, int[] arrayB)
{
    int answer = 0;
    HashSet<int> setA = new HashSet<int>();
    HashSet<int> setB = new HashSet<int>();
    arrayA = arrayA.OrderBy(x => x).ToArray();
    arrayB = arrayB.OrderBy(x => x).ToArray();


    GetDiv(arrayA[0], setA);
    GetDiv(arrayB[0], setB);

    for (int i = 1; i < arrayA.Length; i++)
    {
        foreach (var item in setA.ToArray())
        {
            if (arrayA[i] % item != 0)
                setA.Remove(item);
        }
        foreach (var item in setB.ToArray())
        {
            if (arrayB[i] % item != 0)
                setB.Remove(item);
        }
    }

    // 크로스 체크
    int maxA = 0;
    foreach (var div in setA)
    {
        if (arrayB.All(x => x % div != 0))
            maxA = Math.Max(maxA, div);
    }

    int maxB = 0;
    foreach (var div in setB)
    {
        if (arrayA.All(x => x % div != 0))
            maxB = Math.Max(maxB, div);
    }

    answer = Math.Max(maxA, maxB);
    return answer;
}


public void GetDiv(int num,HashSet<int> h)
{
    for (int i = 1; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            h.Add(i);
            h.Add(num / i);
        }
    }
}