99클럽 코테 스터디 2일차 TIL + Programmers 숫자 카드 나누기 풀이 java

1. 문제 설명

문제링크

2. 접근 방식

keyword: GCD(최대 공약수) 구하는 법 - 유클리드 호제법

ArrayA와 ArrayB의 최대 공약수를 구한다. 최대 공약수를 구하는 방법은 다음과 같다.

1. 맨 처음 값과 두 번째 값 간의 최대 공약수를 구한다. (유클리드 호제법 이용)
2. 1번에서 나온 GCD와 세 번째 값간의 최대 공약수를 구한다.
   (왜 이렇게 구해도 되는거야? - 1번에서 나온 GCD는 이미 1 번째 값과 2 번째 값에서의 최대 공약수 이다.
   만약 해당 GCD로 3 번값이 바로 나누어진다면, GCD가 1,2번과 같은 것이므로, 그대로 가도 된다.
   만약 GCD가 더 작아진다면, 해당 값이 현재까지 3가지 값에서 통하는 GCD 인 것이다.
   이런 식으로 GCD를 갱신해 나가면, 모든 값에서 통하는 GCD를 구할 수 있다.)
3. 1,2번 과정을 배열 전체에 대해서 반복하여 최종적인 GCD를 배열마다 구한다.
4. GCD가 서로의 배열에서 그 무엇도 나눌 수 없는 수인지 확인한다. (GCD가 1인 경우 여기서 통과하지 못한다.)
5. 1~4번 과정을 다 통과한 GCD 중 최대값을 출력한다.

3. 코드 분석

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        // 1. 각 배열의 GCD 구하기 
        int GCD_A = arrayA[0]; int GCD_B = arrayB[0]; 

        for(int i = 1; i<arrayA.length; i++){
            GCD_A = getGCD(GCD_A, arrayA[i]); // 모두에게 통하는 GCD로 갱신됨. 
        }

        for(int i = 1; i<arrayB.length; i++){
            GCD_B = getGCD(GCD_B, arrayB[i]);
        }
        // 2. Cross 해서 남의 GCD로 나눠지는 수가 있는지 체크 있으면 fail 
        for(int i = 0; i<arrayB.length; i++){
            if(arrayB[i]%GCD_A == 0) { GCD_A = 0; break;}
        }

        for(int i = 0; i<arrayA.length; i++){
            if(arrayA[i]%GCD_B == 0) { GCD_B = 0; break;} 
        }

        // 3, 살아남은 GCD 중 가장 큰 값 출력
        int ans = Math.max(GCD_A, GCD_B);
        return ans;
    }

    public int getGCD(int a, int b){
        if(a%b == 0) return b;
        else return getGCD(b, a%b);
    }
}

4. 성장하기

전체 배열에 대해서 성립하는 GCD를 구해야 하는데, 제일 작은 값과 두 번째로 작은 값에서 나온 GCD를 이용해서 문제를 풀었다. 이렇게 되니, 당연히, 배열마다의 정확한 GCD를 구하지 못했고, 그 때문에 문제를 틀렸다.
그냥 임의의 원소 2개의 GCD를 다른 원소들과 비교하며 GCD를 계속 갱신해나간다면, 모든 배열에 대해서 성립하는 GCD를 구할 수 있다는 생각을 하지 못했다. 이번 문제에서 또 하나 배운 것 같다.