[Java] 연습문제 - 숫자 카드 나누기(Lv 2)

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

프로그래머스

 

 

✔ 입출력 예시

숫자 카드 나누기 입출력 예

 

 

💡 포인트

1️⃣ 각 배열(철수, 영희) 배열의 원소를 모두 나눌 수 있는 양의 정수 a 구하기 👉 각 배열의 최대공약수

2️⃣ 각 상대 배열(영희, 철수) 배열의 원소를 모두 나눌 수 없는 양의 정수 a 구하기

3️⃣ arrayA와 arrayB의 길이는 같음

4️⃣ arrayA와 arrayB에는 중복된 원소가 있을 수 있음

 

 

❓ 풀이과정

1️⃣ 철수와 영희의 최대공약수를 담는 변수에 각 배열의 첫번째 원소 담기

2️⃣ 각 배열의 길이가 1보다 클 경우에만 배열을 순회하며 최대공약수 구하기 

     👉 배열의 길이가 1이라면 최대공약수 역시 0번째 원소와 같기 때문

     👉 최대공약수 구하는 알고리즘 : 유클리드 호제법

3️⃣ 두 배열은 길이가 같으므로 arrayA 또는 arrayB의 길이만큼 반복문을 순회하며 2️⃣에서 구한 최대공약수로 서로의

     배열의 원소 중 하나라도 나누어떨어진다면 최대공약수의 값을 0으로 바꾸기

4️⃣ 두 최대공약수 변수 중 가장 큰 값을 return

     👉 3️⃣에서 두 최대공약수 모두 서로의 배열의 원소를  나눈 결과 나머지가 없었다면 0으로 바뀌어 조건을 만족하는

            a가 없는 경우 0을 return한 것과 같게 됨  

 

 

✔ 소스코드

public class Solution {

	private int solution(int[] arrayA, int[] arrayB) {
		int chulsu = arrayA[0];
		
		if(arrayA.length > 1) {
			for (int i = 1; i < arrayA.length; i++) {
				chulsu = gcd(chulsu, arrayA[i]);
			}
		}
		
		int yeonghui = arrayB[0];
		
		if(arrayB.length > 1) {
			for (int i = 1; i < arrayB.length; i++) {
				yeonghui = gcd(yeonghui, arrayB[i]);
			}
		}

		for (int i = 0; i < arrayA.length; i++) {
			if(chulsu != 0 && arrayB[i] % chulsu == 0) {
				chulsu = 0;
			}
			if(yeonghui != 0 && arrayA[i] % yeonghui == 0) {
				yeonghui = 0;
			}
		}
		
		return Math.max(chulsu, yeonghui);
	}
	
	private int gcd(int small, int big) {
			
		if(small > big) {
			int temp = small;
			small = big;
			big = temp;
		}

		if(small == 0) {
			return big;
		}else {
			return gcd(small, big%small);
		}
	}
	
	public static void main(String[] args) {
		Solution main = new Solution();
		
		// result = 0
		int[] arrayA = {10, 17};
		int[] arrayB = {5, 20};
		
		// result = 10
		/*int[] arrayA = {10, 20};
		int[] arrayB = {5, 17};*/

		// result = 7
		/*int[] arrayA = {14, 35, 119};
		int[] arrayB = {18, 30, 102};*/
		
		/*int[] arrayA = {10, 30};
		int[] arrayB = {5, 10, 39};*/
		
		System.out.println(main.solution(arrayA, arrayB));
	}
}

 

 

❗ 실행 결과

숫자 카드 나누기 실행 결과

 

 

유클리드 호제법으로 풀어야한다는 것은 떠올렸지만 유클리드 호제법 구현하는 법이 헷갈려 다시 공부해야했던 문제😂

유클리드 호제법은 매번 small의 값을 big에 담아줘야했던건지, 나머지값을 small에 담아줘야했던건지 헷갈려 구글링을 다시 하게 되는 알고리즘이다...

앞으로도 꾸준히 연습해서 헷갈리지 않을 수 있게 해야지 😊