[프로그래머스] 숫자 카드 나누기 C++

문제 설명

제한 사항 및 입출력 예제

---

알고리즘 개념

- 개념 자체는 간단하다. 두 정수 배열 중 한 배열을 골랐을 때, 그 배열의 공약수 집합들 중 남은 배열의 원소와 나누어 떨어지지 않는 최댓값 원소를 찾는 문제다. 여기서 얼마나 시간을 줄이느냐가 관건이다(즉, 알고리즘을 맞게 작성하였어도 시간 초과가 뜰 수 있다). 필자는 풀이에서 언급할 반복의 횟수를 줄이는 방식을 통해 시간 초과 문제를 해결하였다.

 

풀이

풀이(1) 최초의 풀이 방법

#include <algorithm>
#include <vector>
using namespace std;

int getGCD(int& min, vector<int>& a, vector<int>& b)
{
    bool check = true;
    int max = 0;

    for (int i = 2; i <= min; i++)
    {
        check = true;
        for (int& j : a)
        {
            if (j % i != 0)
            {
                check = false;
                break;
            }
        }

        if (check)
        {
            for (int& j : b)
            {
                if (j % i == 0)
                {
                    check = false;
                    break;
                }
            }

            if (check)
                max = std::max(max, i);
        }
    }

    return max;
}

int solution(vector<int> vA, vector<int> vB)
{
    int mina = *min_element(vA.begin(), vA.end());
    int minb = *min_element(vB.begin(), vB.end());

    return max(getGCD(mina, vA, vB), getGCD(minb, vB, vA));
}

※ 알고리즘

int solution(vector<int> vA, vector<int> vB)
{
    int mina = *min_element(vA.begin(), vA.end());
    int minb = *min_element(vB.begin(), vB.end());

    return max(getGCD(mina, vA, vB), getGCD(minb, vB, vA));
}

- 각 배열의 최솟값을 mina, minb에 초기화한다. 최솟값을 따로 지정하는 이유는 공약수의 성질 중 하나가 원소들 중 최솟값을 넘는 공약수는 존재하지 않는 것이므로 마지막 반복 구간을 배열의 최솟값인 mina, minb으로 지정한다. 

 

- 이 값을 주어진 조건을 만족하는 정수를 구할 함수 getGCD()에 넘겨주고, 이 둘 중 최댓값을 리턴하면 된다.

 

int getGCD(int& min, vector<int>& a, vector<int>& b)
{
    bool check = true;
    int max = 0;
    
	for (int i = 2; i <= min; i++)
    {
        check = true;
        for (int& j : a)
        {
            if (j % i != 0)
            {
                check = false;
                break;
            }
        }

- 배열 a의 공약수들을 찾는 과정이다. 2부터 최솟값까지 a의 원소들을 나눠주는데, 만약 하나라도 나눠지지 않는다면 check 변수를 false로 바꾸고 반복문을 종료한다.

 

        if (check)
        {
            for (int& j : b)
            {
                if (j % i == 0)
                {
                    check = false;
                    break;
                }
            }

            if (check)
                max = std::max(max, i);
        }
    }

    return max;

- 위의 반복을 모두 끝나고도 check가 false가 되지 않았다면, i가 공약수라는 뜻이므로 다른 배열 b의 원소들과 비교를 한다. 만약 하나라도 나눠진다면 배열 b의 약수 중 하나라는 뜻이므로 check를 false로 바꾸고 반복문을 종료한다.

 

- i에 대한 반복이 끝나고 난 후 check 변수가 true라는 것은 배열 a의 공약수이면서 배열 b의 약수가 아니라는 뜻이므로 최댓값으로 지정해주는데, 이전의 저장된 값과 비교하여 큰 값을 max에 초기화해주고 리턴하면 된다.

---

풀이(2) 조금 더 효율적인 방법

#include <algorithm>
#include <vector>
using namespace std;

int getGCD(int& min, vector<int>& a, vector<int>& b)
{
    bool check = true;

    for (int i = min; i > 0; i--)
    {
        check = true;
        for (int& j : a)
        {
            if (j % i != 0)
            {
                check = false;
                break;
            }
        }

        if (check)
        {
            for (int& j : b)
            {
                if (j % i == 0)
                {
                    check = false;
                    break;
                }
            }

            if (check)
                return i;
        }
    }

    return 0;
}

int solution(vector<int> vA, vector<int> vB)
{
    int mina = *min_element(vA.begin(), vA.end());
    int minb = *min_element(vB.begin(), vB.end());

    return max(getGCD(mina, vA, vB), getGCD(minb, vB, vA));
}

- 변한 게 거의 없어 보이지만 반복문이 2부터 시작해 점차 늘어가는 것이 아니라, 최솟값부터 시작해 0까지 점차 줄어드는 것으로 바뀌었다.

 

- 어차피 최댓값만 리턴하면 되므로 max값을 갱신할 필요 없이, 가장 큰 값을 바로 리턴하고 반복을 종료하는 것이 시간적인 측면에서 더욱 효율적일 것이라고 판단했다.

 

왼쪽의 테스트 결과는 풀이(1), 오른쪽의 테스트 결과는 풀이(2)