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

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

문제 설명

철수와 영희가 숫자카드를 받는데

1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

위 두 조건 중 하나를 만족하는 양의 정수 a를 구하려 한다.

철수가 받은 카드배열 arrayA와

영희가 받은 카드배열 arrayB가 주어진다.

접근 방식

최대공약수를 구해서 풀었습니다.

A배열의 최대공약수(gcdA), B배열의 최대공약수(gcdB)를 구한 후

B배열을 돌면서 gcdA로 나눠지는 수가 있는지 확인, 있다면 gcdA는 0

A배열을 돌면서 gcdB로 나눠지는 수가 있는지 확인, 있다면 gcdB는 0

gcdA와 gcdB 중 큰 값을 출력

코드

import java.util.*;

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        
        int leng = arrayA.length;
        
        int gcdA = arrayA[0];
        int gcdB = arrayB[0];

        for(int i = 1; i < leng; i++){
            gcdA = getGCD(arrayA[i], gcdA);
            gcdB = getGCD(arrayB[i], gcdB);
        }
        
        if(gcdA != 0){
            for(int b : arrayB){
                if(b % gcdA == 0) {
                    gcdA = 0;
                    break;
                }
            }
        }
        
        if(gcdB != 0){
            for(int a : arrayA){
                if(a % gcdB == 0){
                    gcdB = 0;
                    break;
                }
            }
        }
        
        answer = Math.max(gcdA, gcdB);
        
        return answer;
    }
    
    private int getGCD(int a, int b){
        int n = 0;
        int tmp = 0;
        if(a < b){
            tmp = a;
            a = b;
            b = tmp;
        }
        
        while(b != 0){
            n = a % b;
            a = b;
            b = n;
        }
        return a;
    
    }
    
}

Disscussion

여러 수의 최대공약수를 구하는 방법과 최대공약수의 성질을 많이 배울 수 있었던 문제였다.
Level2는 아니고 Level2.5정도 되는거 같다…