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

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

프로그래머스

 

 

숫자 카드 나누기

 

A 배열의 가장 큰 나누는 수 구하기

3가지 경우가 존재한다.

풀이 방법

코드

#include <bits/stdc++.h>

using namespace std;
int num1, num2;
int solution(vector<int> arrayA, vector<int> arrayB) {
    //1. 정렬하기
    sort(arrayA.begin(), arrayA.end());
    sort(arrayB.begin(), arrayB.end());
    //2. A 원소들을 공통으로 나누는 수 구하기, 가장 큰 수부터
    for(int i=arrayA[0];i>=2;i--){ //i:나누는 숫자
        int j=0;
        for(j=0;j<arrayA.size();j++){
            if(arrayA[j]%i==0) continue;
            else break;
        }
        if(j==arrayA.size()){ //모든 원소가 i에 나누어지면 num1에 저장
            num1=i; break;
        }
    }
    //B의 원소가 num1에 나눠지는지 확인
    if(num1!=0){
        int j=0;
        for(j=0;j<arrayB.size();j++){
            if(arrayB[j]%num1!=0) continue;
            else break;
        }
        if(j!=arrayB.size()){ //나누어졌다면 B에 num1의 배수가 존재하는 것이므로 num1=0
            num1=0;
        }
    }
    //3. B 원소들을 공통으로 나누는 수 구하기, 가장 큰 수부터
    for(int i=arrayB[0];i>=2;i--){
        int j=0;
        for(j=0;j<arrayB.size();j++){
            if(arrayB[j]%i==0) continue;
            else break;
        }
        if(j==arrayB.size()){//모든 원소가 i에 나누어지면 num2에 저장
            num2=i; break;
        }
    }
    //A의 원소가 num2에 나눠지는지 확인
    if(num2!=0){
        int j=0;
        for(j=0;j<arrayA.size();j++){
            if(arrayA[j]%num2!=0) continue;
            else break;
        }
        if(j!=arrayA.size()){ //나누어졌다면 B에 num2의 배수가 존재하는 것이므로 num2=0
            num2=0;
        }
    }
    //4. num1과 num2 중 더 큰 수 리턴 
    if(num1>=num2) return num1;
    else return num2;

}

아닐수도 있어여..지적 환영..

 

더 쉬운 방법 - gcd(최대공약수) 코드 이용하기

#include <bits/stdc++.h>

using namespace std;
int num1, num2;

int gcd(int a, int b){
    if(b==0) return a;
    int result = gcd(b,a%b);
    return result;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    //이번에는 gcd 함수 이용! - A의 최대공약수 찾기
    num1=arrayA[0];
    for(int i=1;i<arrayA.size();i++){
        num1 =gcd(num1, arrayA[i]);
    }
        
    //B의 원소가 num1에 나눠지는지 확인
    if(num1!=0){
        int j=0;
        for(j=0;j<arrayB.size();j++){
            if(arrayB[j]%num1!=0) continue;
            else break;
        }
        if(j!=arrayB.size()){ //나누어졌다면 B에 num1의 배수가 존재하는 것이므로 num1=0
            num1=0;
        }
    }
    //2. B의 최대공약수 찾기
    num2=arrayB[0];
    for(int i=1;i<arrayB.size();i++){
        num2 =gcd(num2, arrayB[i]);
    }
   
    //A의 원소가 num2에 나눠지는지 확인
    if(num2!=0){
        int j=0;
        for(j=0;j<arrayA.size();j++){
            if(arrayA[j]%num2!=0) continue;
            else break;
        }
        if(j!=arrayA.size()){ //나누어졌다면 B에 num2의 배수가 존재하는 것이므로 num2=0
            num2=0;
        }
    }
    //3. num1과 num2 중 더 큰 수 리턴 
    if(num1>=num2) return num1;
    else return num2;

}