[programmers] 숫자 카드 나누기

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

공통 인수 찾기

 

---------------------------------------------------풀이----------------------------------------------------

 

맨 처음 arrayA와 arrayB를 오름차순이 되도록 sorting한다.

(이 방식을 거치지 않아도 통과는 되지만, 시간 차이가 매우 많이 나니까 하는 것이 좋을 것 같다.)

 

우선, get_common_factor() 함수를 이용해 arrayA의 공통인수를 찾는다.

이 함수에서는 arrayA를 모두 나눌 수 있는 수를 찾는 것이므로, arrayA[0](arrayA의 가장 작은 값)부터 2(나눌 수 있는 최소)까지를 비교한다.

각 값이 arrayA의 원소를 모두 나눌 수 있는지 all_divided()함수를 이용해 비교해 true이면 vector에 저장한다.

이렇게 하면 큰 값부터 내림차순으로 공통인수가 저장될 것이다.

all_divided()함수에서는 arrayA의 맨 뒤 가장 큰 값부터 factor로 나누어지는지를 비교해 true/false를 리턴한다.

 

이렇게 찾은 공통 인수들이 내림차순으로 저장된 common_factor 벡터를 얻었다.

여기에 공통 인수가 존재한다면, 큰 공통 인수부터 사용해 arrayB의 하나라도 나눌 수 있는지 체크한다.

is_factor_of()함수를 사용해 arrayB의 큰 값부터 나누어지는지 체크하고, true/false를 리턴한다.

모두 나눌 수 없다면 이 수가 정답이고, 더 작은 공통 인수에 대해서는 비교할 필요가 없으므로 종료한다.

 

같은 작업을 arrayB에 대해서도 수행한다.

 

모두 수행 후, 더 큰 값을 answer에 저장해 리턴한다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool all_divided(vector<int> &arr, int factor){
    for(int i = 0; i < arr.size(); i++){
        if(arr[arr.size()-1-i] % factor != 0){
            return false;
        }
    }
    return true;
}

// arr의 모든 공통 인수를 리턴.
vector<int> get_common_factor(vector<int> &arr){
    vector<int> com_fac;
    
    for(int i = arr[0]; i > 1; i--){
        if(all_divided(arr, i)){
            com_fac.push_back(i);
        }
    }
    
    return com_fac;
}

// factor가 arr의 원소들 중 인수가 되는지 리턴.
bool is_factor_of(int factor, vector<int> &arr){
    // 큰 수부터 계산
    for(int i = 0; i < arr.size(); i++){
        if(arr[arr.size()-1-i] % factor == 0){
            return true;
        }
    }
    return false;
}

// arrayA(B)의 인수이면서 arrayB(A)의 인수가 아닌 가장 큰 양의 정수=?
// 없다면 0 리턴.
int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    sort(arrayA.begin(), arrayA.end());
    sort(arrayB.begin(), arrayB.end());
    // arrayA의 공통인수가 존재한다면,
    vector<int> common_factor = get_common_factor(arrayA);
    if(!common_factor.empty()){
        // 큰 수부터 비교
        for(int i = 0; i < common_factor.size(); i++){
            // arrayB의 인수가 아니라면 answer.
            if(!is_factor_of(common_factor[i], arrayB)){
                answer = common_factor[i];
                break;
            }
        }
    }
    // arrayB의 공통 인수가 존재한다면,
    common_factor.clear();
    common_factor = get_common_factor(arrayB);
    if(!common_factor.empty()){
        // 큰 수부터 비교
        for(int i = 0; i < common_factor.size(); i++){
            // arrayA의 인수가 아니라면 answer.
            if(!is_factor_of(common_factor[i], arrayA)){
                if(answer < common_factor[i]){
                    answer = common_factor[i];
                }
                break;
            }
        }
    }
    
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

맨 처음 생각한건 수학 이론으로 공통 인수를 찾는 방식이었는데, 그 방법을 쓰지 않고 단순 비교로도 통과는 된다.

최대공약수를 찾는게 '유클리드 호제법'이던데 이 방식을 알아는 두자.

다만, 정렬을 잘 이용해서 최소의 비교만 한다면, 문제가 요구하는 바는 맞출 수 있다는거!

(솔직히 통과되는 것에 놀랐다)