🎯문제
철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.
- 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
- 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
예를 들어, 카드들에 10, 5, 20, 17이 적혀 있는 경우에 대해 생각해 봅시다. 만약, 철수가 [10, 17]이 적힌 카드를 갖고, 영희가 [5, 20]이 적힌 카드를 갖는다면 두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. 하지만, 철수가 [10, 20]이 적힌 카드를 갖고, 영희가 [5, 17]이 적힌 카드를 갖는다면, 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없습니다. 따라서 철수와 영희는 각각 [10, 20]이 적힌 카드, [5, 17]이 적힌 카드로 나눠 가졌다면 조건에 해당하는 양의 정수 a는 10이 됩니다.
철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return하도록 solution 함수를 완성해 주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.
제한사항
제한사항
- 1 ≤ arrayA의 길이 = arrayB의 길이 ≤ 500,000
- 1 ≤ arrayA의 원소, arrayB의 원소 ≤ 100,000,000
- arrayA와 arrayB에는 중복된 원소가 있을 수 있습니다.
입출력 예
| arrayA | arrayB | result |
|---|---|---|
| [10, 17] | [5, 20] | 0 |
| [10, 20] | [5, 17] | 10 |
| [14, 35, 119] | [18, 30, 102] | 7 |
입출력 예 설명
입출력 예 #1
- 문제 예시와 같습니다.
입출력 예 #2
- 문제 예시와 같습니다.
입출력 예 #3
- 철수가 가진 카드에 적힌 숫자들은 모두 3으로 나눌 수 없고, 영희가 가진 카드에 적힌 숫자는 모두 3으로 나눌 수 있습니다. 따라서 3은 조건에 해당하는 양의 정수입니다. 하지만, 철수가 가진 카드들에 적힌 숫자들은 모두 7로 나눌 수 있고, 영희가 가진 카드들에 적힌 숫자는 모두 7로 나눌 수 없습니다. 따라서 최대값인 7을 return 합니다.
✏️풀이
코드
import java.util.*;
class Solution {
// 유클리드 호제법을 사용하여 최대공약수를 구하는 메서드
public int gcd(int a, int b) {
if(b == 0)
return a;
else
return gcd(b, a % b);
}
// array에 있는 값들이 div로 나누어지는지 판단하는 메서드
public boolean check(int[] array, int div) {
for(int n : array)
if(n % div == 0)
return true;
return false;
}
public int solution(int[] arrayA, int[] arrayB) {
int answer = 0;
// 배열을 정렬
Arrays.sort(arrayA);
Arrays.sort(arrayB);
// 배열 중 가장 작은 값으로 초기화
int gcdA = arrayA[0];
int gcdB = arrayB[0];
// gcd 메서드를 사용해서 최대공약수를 구함
for(int i = 1; i < arrayA.length; i++) {
gcdA = gcd(arrayA[i], gcdA);
gcdB = gcd(arrayB[i], gcdB);
}
// A 배열이 B의 값으로 나누어지는지 확인
if(!check(arrayA, gcdB))
answer = Math.max(answer, gcdB);
// B 배열이 A의 값으로 나누어지는지 확인
if(!check(arrayB, gcdA))
answer = Math.max(answer, gcdA);
return answer;
}
}설명
메서드의 구현을 통해 진행하였다.
gcd 메서드는 유클리드 호제법을 사용하여 최대공약수를 구하는 메서드이다. 매개변수로 값을 2개를 받고 뒤에 있는 값이 0이라면 a가 두 수의 최대공약수가 되는 방식이다.
예를 들어, 48과 18이라는 값이 들어갔다고 하면
(48, 18)
18 != 0 이므로 gcd(18, 48 % 18) 재귀 호출
-> (18, 12)
12 != 0 이므로 gcd(12, 18 % 12) 재귀 호출
-> (12, 6)
6 != 0 이므로 gcd(6, 12 % 6) 재귀 호출
-> (6, 0)
0 == 0 이므로 6을 반환
즉 48과 18의 최대공약수는 6이 되는 것이다.
check 메서드는 배열과 숫자를 넘겨주고 해당 배열의 모든 값을 숫자로 나눠보면서 배열의 값 중 하나라도 나눠지는 값이 있다면 true를 모든 값이 나눠지지 않는다면 false를 반환하는 메서드이다.
위의 두 메서드를 사용해 문제를 해결해보고자 한다. 우선 gcd 메서드를 사용해서 최대공약수를 구하기 위해 배열을 정렬을 시켜준다. 이후 gcdA, gcdB를 통해 배열 A의 최대공약수와 배열 B의 최대공약수를 저장할 변수를 선언해준다.
gcd 메서드를 사용해서 각각 배열의 최대공약수를 구해준다. 반복이 끝나면 배열 A의 최대공약수와 배열 B의 최대공약수가 각각 gcdA, gcdB에 저장이 될 것이다.
이후 check 메서드를 사용한다. 배열 A와 gcdB를 매개변수로 넘겨주어 배열 A의 값들 중 gcdB로 나누어떨어지는 값이 있는지 확인을 진행한다. 만약 단 하나라도 나누어떨어지는 값이 있다면 조건에 만족하지 않기 때문이다. 첫번째 비교가 끝나면 이번에는 배열 B와 gcdA를 넘겨주고 배열 B의 값들 중 gcdA로 나누어떨어지는 값이 있는지 확인한다.
이를 통해 가장 큰 양의 정수 a를 구하는 문제를 해결할 수 있다!
💡느낀 점
처음 문제를 읽으면서 유클리드 호제법이 생각나지 않아 반복문을 통해 문제를 해결하려고 했다. 그러나 코드를 짜면서 너무 복잡하고 시간초과가 걸릴 것 같아서 바로 포기를 하고 다른 방법을 모색하였다. 그렇게 하다보니 유클리드 호제법이 생각이 났고, 많이 까먹었기에 다른 블로그를 참고해서 문제를 해결할 수 있었다. 유클리드 호제법 또한 코테를 준비할 때 너무나 기초적인 것인데 존재조차 까먹고 있었기 때문에 민망했다.. 더 열심히 공부해야겠다!
링크
