Programmers | Level 2 | 숫자 카드 나누기
Programmers | Level 2 | 숫자 카드 나누기
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Math
Description
철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 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 해 주세요.
Constraints
- 1 ≤
arrayA의 길이 =arrayB의 길이 ≤ 500,000 - 1 ≤
arrayA의 원소,arrayB의 원소 ≤ 100,000,000 arrayA와arrayB에는 중복된 원소가 있을 수 있습니다.
Examples
| arrayA | arrayB | result |
|---|---|---|
[10, 17] | [5, 20] | 0 |
[10, 20] | [5, 17] | 10 |
[14, 35, 119] | [18, 30, 102] | 7 |
Solutions
Code
import java.util.*;
class Solution {
// solution 메서드: arrayA와 arrayB에서 조건을 만족하는 가장 큰 양의 정수 a를 반환
public int solution(int[] arrayA, int[] arrayB) {
int gcdA = arrayA[0]; // arrayA에서의 GCD 초기화
int gcdB = arrayB[0]; // arrayB에서의 GCD 초기화
int n = arrayA.length;
// arrayA의 모든 숫자에 대해 GCD 계산
for (int i = 1; i < n; i++) {
gcdA = gcd(gcdA, arrayA[i]);
if (gcdA == 1) break; // GCD가 1이면 더 이상 계산 필요 없음
}
// arrayB의 모든 숫자에 대해 GCD 계산
for (int i = 1; i < n; i++) {
gcdB = gcd(gcdB, arrayB[i]);
if (gcdB == 1) break; // GCD가 1이면 더 이상 계산 필요 없음
}
// 각각의 GCD에 대해 다른 배열에서 조건을 만족하는지 확인
int resultA = maxNonDiv(gcdA, arrayB);
int resultB = maxNonDiv(gcdB, arrayA);
// 두 결과 중 큰 값을 반환
return Math.max(resultA, resultB);
}
// 주어진 GCD가 array에 있는 수들로 나누어지지 않는 가장 큰 수를 찾는 함수
private int maxNonDiv(int gcd, int[] arr) {
for (int i = gcd; i > 1; i--) {
if (gcd % i == 0 && !isDividen(arr, i)) { // gcd가 i로 나누어지고 arr의 요소는 i로 나누어지지 않으면
return i; // 조건을 만족하는 가장 큰 i 반환
}
}
return 0; // 조건을 만족하는 값이 없을 경우 0 반환
}
// 배열의 모든 요소가 주어진 값으로 나누어지는지 확인하는 함수
private boolean isDividen(int[] arr, int div) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] % div == 0) return true; // 하나라도 나누어지면 true
}
return false; // 전부 나누어지지 않으면 false
}
// 두 수의 최대공약수를 구하는 함수 (유클리드 호제법 사용)
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a; // GCD 반환
}
}
Approach
이 문제는 배열 A와 배열 B의 숫자들에 대해 각각의 최대공약수(GCD)를 구하고, 다른 배열의 수들이 그 최대공약수로 나눠지지 않는 가장 큰 값을 찾는 방식입니다. 유클리드 호제법을 이용해 각 배열의 최대공약수를 구하고, 조건을 만족하는 최대 값을 찾아 반환합니다.
1. 문제 분석
철수와 영희가 가진 숫자 카드에서 특정 조건을 만족하는 가장 큰 정수 a를 찾는 문제입니다. 여기서 철수의 카드 숫자들을 모두 나눌 수 있는 수 중, 영희의 카드에 적힌 숫자를 나눌 수 없는 가장 큰 수를 찾는 방식입니다. 반대로, 영희의 카드에서 조건을 만족하는 값도 같은 방식으로 찾습니다. 이를 위해 각각의 카드 집합에서 최대공약수를 구하고, 상대방의 카드와 비교하는 방식으로 문제를 해결할 수 있습니다.
2. 접근 방식
이 문제를 풀기 위해서는 먼저 최대공약수를 계산한 후, 이를 이용해 상대방의 카드에서 조건을 만족하는지 확인하는 과정을 거칩니다. 각 단계는 다음과 같이 구성됩니다.
- 최대공약수 계산: 먼저, 철수와 영희가 가진 카드 숫자들에서 각각 모든 숫자를 나눌 수 있는 가장 큰 수를 계산합니다. 최대공약수는 여러 수에서 공통으로 나눌 수 있는 가장 큰 값을 의미하며, 이 값은 각 카드 집합에서 모든 숫자를 나눌 수 있는 가장 큰 공통 분모가 됩니다. 이 값을 구한 후, 각 카드 집합에서 모든 숫자를 나눌 수 있는 공통된 값을 찾는 것이 첫 번째 단계입니다.
- 조건 만족 여부 확인: 두 번째 단계는 구한 최대공약수가 상대방이 가진 카드 숫자들 중 어느 것에도 나누어지지 않는지 확인하는 과정입니다. 즉, 철수의 카드에서 구한 값이 영희의 카드 중 어떤 숫자도 나눌 수 없어야 하고, 반대로 영희의 카드에서 구한 값이 철수의 카드 숫자 중 어떤 것도 나눌 수 없어야 합니다. 이 과정을 통해 조건을 만족하는 값을 찾습니다.
- 최종 선택: 마지막으로, 두 가지 조건을 만족하는 값 중에서 더 큰 값을 선택합니다. 철수와 영희 각각의 카드에서 조건을 만족하는 값이 있을 경우, 그 중에서 더 큰 값을 최종적으로 선택해 반환합니다. 만약 조건을 만족하는 값이 없다면 결과는
0이 됩니다.
3. GCD 계산 과정
먼저, 각 배열의 숫자를 모두 나눌 수 있는 가장 큰 공통분모를 찾아야 합니다. 즉, 철수와 영희가 가진 카드에서 공통적으로 나눌 수 있는 최대공약수를 구하는 것이 핵심입니다. 이 최대공약수를 통해, 배열 내의 숫자들이 어떤 수로 나눌 수 있는지를 확인하고, 상대방 배열의 숫자들과 비교하는 작업을 수행할 수 있습니다.
먼저, 두 수의 최대공약수를 구하는 함수를 구현합니다. 유클리드 호제법을 사용하여 두 수의 최대공약수를 효율적으로 구할 수 있습니다. 이 방법은 두 수의 나머지를 구하면서 반복적으로 최대공약수를 계산해 나가는 방식입니다.
// 두 수의 최대공약수 계산 (유클리드 호제법)
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a; // GCD 반환
}
이제 이 gcd() 함수를 사용하여 각 배열의 모든 숫자들의 최대공약수를 구합니다. 주어진 두 배열에서 각각 첫 번째 요소를 초기 값으로 설정한 후, 나머지 요소들과 차례대로 최대공약수를 계산합니다. 만약 최대공약수가 1이 된다면, 더 이상 공통으로 나눌 수 있는 수가 없다는 의미이므로 반복을 중단할 수 있습니다.
int gcdA = arrayA[0]; // arrayA의 첫 번째 값을 초기 GCD로 설정
int gcdB = arrayB[0]; // arrayB의 첫 번째 값을 초기 GCD로 설정
int n = arrayA.length;
// arrayA의 모든 숫자에 대해 GCD 계산
for (int i = 1; i < n; i++) {
gcdA = gcd(gcdA, arrayA[i]); // GCD 계산
if (gcdA == 1) break; // GCD가 1이면 더 이상의 공통 나눗셈이 없음
}
// arrayB의 모든 숫자에 대해 GCD 계산
for (int i = 1; i < n; i++) {
gcdB = gcd(gcdB, arrayB[i]);
if (gcdB == 1) break;
}
이 과정을 통해 arrayA와 arrayB에서 각각의 모든 원소들을 나눌 수 있는 최대공약수를 구할 수 있습니다. 이 값들은 이후 단계에서 상대방의 카드와 비교하여 조건을 만족하는지 확인하는 중요한 역할을 하게 됩니다.
4. 상대 배열에서 조건 만족 여부 확인
이 단계에서는 이전에 구한 최대공약수를 활용해 상대방의 카드 숫자들 중 어느 것에도 나눠지지 않는 가장 큰 수를 찾는 것이 목표입니다. 먼저, 각 카드 집합에서 구한 공약수 중에서 상대방 카드 집합에서 조건을 만족하는 가장 큰 값을 찾습니다.
상대방의 카드 집합과 비교할 때, 먼저 최대공약수를 기준으로 조건을 만족하는지 확인합니다. 만약 최대공약수가 조건을 만족하지 않는다면, 그보다 작은 공약수들을 하나씩 차례로 검사해 조건을 만족하는 가장 큰 값을 찾아야 합니다. 중요한 것은, 공약수가 한쪽 카드 집합에서는 모든 숫자를 나눌 수 있어야 하며, 동시에 상대방 카드 집합의 어느 숫자도 나눌 수 없어야 한다는 점입니다.
private int maxNonDiv(int gcd, int[] arr) {
for (int i = gcd; i > 1; i--) { // GCD 값보다 작은 값들로 확인
if (gcd % i == 0 && !isDividen(arr, i)) { // i가 gcd의 약수이면서, 상대 배열의 어느 수로도 나눌 수 없는 경우
return i; // 조건을 만족하는 가장 큰 i 반환
}
}
return 0; // 조건을 만족하는 값이 없을 경우 0 반환
}
// 배열의 모든 요소가 주어진 값으로 나누어지는지 확인하는 함수
private boolean isDividen(int[] arr, int div) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] % div == 0) return true; // 하나라도 나누어지면 true
}
return false; // 전부 나누어지지 않으면 false
}
이 함수는 최대공약수부터 시작해 그보다 작은 공약수들을 차례로 확인하면서, 상대방의 카드 숫자들과 나눌 수 없는 수를 찾는 역할을 합니다. 만약 조건을 만족하는 값이 없을 경우, 결과는 0이 됩니다. 공약수가 상대방의 카드 집합에서 나눌 수 없는 가장 큰 수일 때, 그 값을 반환하게 됩니다. 이 과정을 철수와 영희의 카드 집합 각각에 대해 적용하여 두 경우를 구할 수 있습니다.
int resultA = maxNonDiv(gcdA, arrayB); // 철수의 공약수가 영희의 카드에서 나눌 수 없는 가장 큰 수인지 확인
int resultB = maxNonDiv(gcdB, arrayA); // 영희의 공약수가 철수의 카드에서 나눌 수 없는 가장 큰 수인지 확인
이 두 결과는 철수와 영희가 가진 카드 집합에서 구한 공약수들 중, 상대방 카드에서 조건을 만족하는 가장 큰 값을 각각 나타냅니다. 이를 통해 두 카드 집합에서 조건을 만족하는 공약수를 찾고, 최종 결과로 사용할 수 있습니다.
5. 최종 결과 선택
이제, 앞서 계산된 두 가지 경우 중 조건을 만족하는 가장 큰 값을 선택하여 최종적으로 반환하게 됩니다. 만약 두 값 모두 조건을 만족하지 않는다면, 즉 조건을 만족하는 공약수가 없다면 결과는 0이 됩니다. 이 단계에서는 최적의 값을 선택하여 문제에서 요구하는 조건을 충족시킵니다.
// 두 결과 중 더 큰 값을 반환, 둘 다 조건을 만족하지 않으면 0 반환
return Math.max(resultA, resultB);
Complexity
- ⏳ TC: O(n)
- 💾 SC: O(1)
각 배열의 모든 숫자에 대해 최대공약수를 구한 뒤, 그 값을 바탕으로 상대방 배열에서 조건을 확인하는 과정에서 시간 복잡도가 결정됩니다. 배열의 길이를 n이라고 할 때, 최대공약수를 구하는 과정과 조건을 확인하는 과정 모두 배열의 크기에 비례하여 수행되므로, 전체 시간 복잡도는 O(n)입니다. 추가적인 자료구조를 사용하지 않기 때문에, 공간 복잡도는 O(1)입니다.
- Algorithm
- Math