20240226_숫자 카드 나누기(프로그래머스)

오늘의 TIL은 숫자 카드 나누기이라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

프로그래머스

 

문제 설명

실제 문제는 좀 더 예시를 들어서 설명해주지만, 중요한 내용만 추리면 아래와 같다.

숫자 배열이 2개 주어지는 경우에 한 배열의 공약수들 중에서 다른 배열의 공약수가 아닌 수 중에 가장 큰 수를 찾으시오.

 

 

제한 조건

1 <= 두 배열의 길이 <= 500,000

1 <= 두 배열의 원소 <= 100,000,000

두 배열에는 중복된 원소가 있을 수 있다.

 

 

해결 방안

1. 두 배열의 최대 공약수를 각각 구한다.

2. 이 최대 공약수를 가지고 각각 다른 배열에 대하여 나눌 수 없는 제일 큰 수를 각각 구한다.

3. 구한 두 수 중에서 큰 값을 a로 return한다.

 

 

통과한 답안

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        
        int GCDA = arrayA[0];
        for (int i = 1; i < arrayA.Length; i++)
        {
            GCDA = FindGCD(GCDA, arrayA[i]);
        }

        int GCDB = arrayB[0];
        for (int i = 1; i < arrayB.Length; i++)
        {
            GCDB = FindGCD(GCDB, arrayB[i]);
        }

        int maxA = 0;
        int maxB = 0;

        for (int i = GCDA; i >= 1; i--)
        {
            if (GCDA % i == 0 && !IsDivisible(i, arrayB))
            {
                maxA = i;
                break;
            }
        }
        for (int i = GCDB; i >= 1; i--)
        {
            if (GCDB % i == 0 && !IsDivisible(i, arrayA))
            {
                maxB = i;
                break;
            }
        }

        answer = (maxA > maxB) ? maxA : maxB;

        return answer;
    }

    public static int FindGCD(int a, int b)
    {
        while (b != 0)
        {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    public static bool IsDivisible(int num, int[] array)
    {
        foreach (int i in array)
        {
            if (i % num == 0)
                return true;
        }
        return false;
    }
}

 

 

최대 공약수를 구하는 로직

public static int FindGCD(int a, int b)
{
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

알고리즘 문제를 푸는데 많이 사용하는 최대공약수를 구하는 로직

 

 

 배열을 나눌 수 있는 숫자인지 확인하는 로직

public static bool IsDivisible(int num, int[] array)
{
    foreach (int i in array)
    {
        if (i % num == 0)
            return true;
    }
    return false;
}

 

숫자를 구했을 때, 이 숫자가 배열을 나눌 수 있는 숫자인지 확인하는 로직

(이것도 알고리즘 문제를 푸는데 사용하는 경우가 있다)

 

 

두 배열의 최대 공약수를 구하는 과정

int GCDA = arrayA[0];
for (int i = 1; i < arrayA.Length; i++)
{
    GCDA = FindGCD(GCDA, arrayA[i]);
}

int GCDB = arrayB[0];
for (int i = 1; i < arrayB.Length; i++)
{
    GCDB = FindGCD(GCDB, arrayB[i]);
}

 

각각 두 배열에 대하여 최대 공약수를 구한다.

 

 

int maxA = 0;
int maxB = 0;

for (int i = GCDA; i >= 1; i--)
{
    if (GCDA % i == 0 && !IsDivisible(i, arrayB))
    {
        maxA = i;
        break;
    }
}
for (int i = GCDB; i >= 1; i--)
{
    if (GCDB % i == 0 && !IsDivisible(i, arrayA))
    {
        maxB = i;
        break;
    }
}

answer = (maxA > maxB) ? maxA : maxB;

 

배열 A의 공약수 중에서 배열 B를 나누지 못하는 최대값 maxA와

배열 B의 공약수 중에서 배열 A를 나누지 못하는 최대값 maxB를 구한다.

 

여기서 각각 최대 공약수를 가지고 반대쪽 배열의 값과 비교하며 나눌 수 있는 숫자인지 확인하는 과정을 거친다.

이 과정을 통해서 A배열은 나눌 수 있지만 B 배열을 나눌 수 없는 가장 큰 값 maxA와

그 반대의 값 maxB를 구할 수 있게된다.

 

이후에 이 두 값 중에서 큰 값을 answer로 return하면 된다.

(만약 이를 충족하는 값이 없다면 기본값으로 maxA와 maxB를 0으로 선언하므로, 0이 return된다)

 

 

오늘은 재미있는 카드놀이 문제인지 알고 접근했던 배열 2개의 공약수와 관련된 문제였던

 

'숫자 카드 나누기' 문제를 기록했는데, 제목과 초기의 내용은 카드를 나눠주는 방법을 찾는 문제라고 생각했지만,

 

실제로는 공약수의 특징을 묻는 문제로 수학으로 가득찬 문제였다.

 

문제를 풀면서도 처음에는 최대 공약수와 공약수들을 구하는 리스트를 구해서 이들을 가지고

 

중복되는 값을 제외하거나 리스트에서 반대편 공약수들을 제거하는 등의 작업을 해봤지만,

 

결국 해결하지 못하고 위의 방법으로 하나의 최대공약수를 가지고 다른 배열의 값들을 나눠서 값을 구하는 방식으로 풀이하였다.