[프로그래머스/JAVA]숫자 카드 나누기

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

프로그래머스

 

 

요즘 문제를 풀면 생각 조금 하다가 한 번에 안풀리면 다른 사람들의 접근 방법을 보고 따라하다보니 이도저도 아닌 것 같아서 끝까지 붙잡아보기로 했다. 레벨2인데도 왜 이렇게 어려운가...

주먹구구식으로 푸느라 코드 반복도 많고 전체적으로 잘 짠 코드의 느낌은 안든다.

 

 

사고과정

문제를 읽고 처음 든 생각은 일단 최대공배수를 구해야겠다는 것이었다. ' 가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고' <- 최대공약수를 구하라고 외치는 중

일단 arrayA와 arrayB의 최대공약수를 구했다. 그럼 이제 이 최대공약수의 약수 중 상대의 카드들을 하나도 나눌 수 없는 양의 정수를 구해야한다.

처음 생각한건 최대공약수를 소인수분해 후 이들을 조합하여 나올 수 있는 경우의 수를 set에 담은 후 상대 카드들과 일일이 비교하는 것이다. 구현하려면 할 수야 있겠지만 생각만해도 시간이 오래걸릴 것 같음

최대공약수만 구해놓고 그 뒤를 어떻게 구해야하나 고민하고있었는데 갑자기 계시가 내려왔다(?)

생각해보니 최대공약수는 일단 나올 수 있는 가장 큰 수다. 이 수로 나눴을 때 나눠진다면 이 수보다 작은 다른 약수로 나눴을 때도 나눠질 수밖에 없다...!

그래서 상대 카드들과 최대공약수를 비교하여 나눠지지 않는 경우에 정답 후보가 된다(철수랑 영희 각각 비교해준 뒤 둘 중에 더 큰 수가 결과가 된다.)

 

 

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        int gcdA = 0, gcdB = 0;
        int a = arrayA[0], b = 0;
        for(int i=1; i<arrayA.length; i++) {
        	b = arrayA[i];
        	int c = 0;
        	while(a > 0) {
        		c = a;
        		a = b%a;
        		b = c;
        	}
        	a = b;
        }
        gcdA = a;
        
        a = arrayB[0];
        for(int i=1; i<arrayB.length; i++) {
        	b = arrayB[i];
        	int c = 0;
        	while(a > 0) {
        		c = a;
        		a = b%a;
        		b = c;
        	}
        	a = b;
        }
        gcdB = a;
        
        if(gcdB > 1) {
        	boolean flg = true;
	        for(int i=0; i<arrayA.length; i++) {
	        	if(arrayA[i]%gcdB == 0) {
	        		flg = false;
	        		break;
	        	}
	        }
	        if(flg) answer = gcdB;
        
        }
        if(gcdA > 1) {
        	boolean flg = true;
        	for(int i=0; i<arrayB.length; i++) {
	        	if(arrayB[i]%gcdA == 0) {
	        		flg = false;
	        		break;
	        	}
	        }
	        if(flg) answer = answer > gcdA ? answer : gcdA;
        }
        
        
        return answer;
    }
}

 

 

위의 코드에서 중복되는 부분을 함수로 빼서 조금 더 간단히 만들어봤다.

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        int gcdA = 0, gcdB = 0;
        int a = arrayA[0], b = 0;
        
        gcdA = gcd(arrayA);
        gcdB = gcd(arrayB);
        
        if(gcdB > 1) answer = findAnswer(arrayA, gcdB);

        if(gcdA > 1) {
        	int tmp = findAnswer(arrayB, gcdA);
        	answer = answer > tmp ? answer : tmp;
        }
        return answer;
    }
	public int gcd(int[] array) {
		int a = array[0];
		int b = 0;
		for(int i=1; i<array.length; i++) {
        	b = array[i];
        	int c = 0;
        	while(a > 0) {
        		c = a;
        		a = b%a;
        		b = c;
        	}
        	a = b;
        }
		return a;
	}
	public int findAnswer(int[] array, int gcd) {
		boolean flg = true;
        for(int i=0; i<array.length; i++) {
        	if(array[i]%gcd == 0) {
        		flg = false;
        		break;
        	}
        }
        if(flg) return gcd;
        else return 0;
	}
}