[HackerRank] 두 집합 사이/Between Two Sets

문제 설명

두 개의 정수 배열이 주어집니다.
다음 두 가지 조건을 만족하는 모든 정수를 찾아 개수를 반환하세요.

1️⃣ 배열 a의 모든 요소가 해당 정수의 약수여야 한다.

• 즉, 그 정수는 a의 모든 요소로 나누어 떨어져야 합니다.

2️⃣ 해당 정수는 배열 b의 모든 요소의 약수여야 한다.

• 즉, b의 모든 요소는 그 정수로 나누어 떨어져야 합니다.

이러한 숫자들을 두 배열 사이에 있는 숫자(between the sets) 라고 합니다.
이 숫자들의 개수를 반환하면 됩니다.

---

입력 형식

• 첫 번째 줄에는 두 개의 정수 n과 m이 주어집니다. (n은 배열 a의 크기, m은 배열 b의 크기)
• 두 번째 줄에는 n개의 정수로 이루어진 배열 a가 주어집니다.
• 세 번째 줄에는 m개의 정수로 이루어진 배열 b가 주어집니다.

제한 조건

---

출력 형식

• 두 배열 사이의 숫자의 개수를 정수로 출력하세요.

---

예제

입력

      
      
      
    
2 3
2 4
16 32 96

 

출력

 

      
      
      
    
3

설명

• 배열 a = [2, 4]
• 배열 b = [16, 32, 96]
• a의 모든 요소의 배수이면서 b의 모든 요소의 약수인 숫자를 찾습니다.
• 가능한 숫자: 4, 8, 16
• 결과: 3

---

 

🔹 해결 방법

1️⃣ 배열 a의 최소공배수(LCM)를 구한다.

• a의 모든 요소를 나눌 수 있는 가장 작은 공배수를 찾기

2️⃣ 배열 b의 최대공약수(GCD)를 구한다.

• b의 모든 요소를 나눌 수 있는 가장 큰 공약수를 찾기

3️⃣ LCM과 GCD 사이의 숫자 중에서 조건을 만족하는 개수를 센다.

• LCM(a)의 배수이면서
• GCD(b)의 약수인 숫자 찾기

---

🔹 코드 구현

      
      
      
    
function gcd(x, y) {
    while (y !== 0) {
        let temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

function lcm(x, y) {
    return (x * y) / gcd(x, y);
}

function getTotalX(a, b) {
    // 1. 배열 a의 최소공배수(LCM) 구하기
    let lcmA = a.reduce((acc, num) => lcm(acc, num));

    // 2. 배열 b의 최대공약수(GCD) 구하기
    let gcdB = b.reduce((acc, num) => gcd(acc, num));

    // 3. LCM과 GCD 사이에서 조건을 만족하는 숫자 개수 찾기
    let count = 0;
    for (let i = lcmA; i <= gcdB; i += lcmA) {
        if (gcdB % i === 0) {
            count++;
        }
    }

    return count;
}

 

 

🔹 코드 설명

1️⃣ gcd(x, y) 함수

• **최대공약수(GCD)**를 구하는 함수

2️⃣ lcm(x, y) 함수

• **최소공배수(LCM)**을 구하는 함수

3️⃣ getTotalX(a, b) 함수

1. 배열 a의 LCM 구하기
   → reduce()를 사용해서 모든 요소들의 LCM을 계산
   → LCM(a) 값이 구해짐
2. 배열 b의 GCD 구하기
   → reduce()를 사용해서 모든 요소들의 GCD를 계산
   → GCD(b) 값이 구해짐
3. LCM과 GCD 사이의 숫자 중에서 조건을 만족하는 숫자 개수 찾기
   • lcmA부터 gcdB까지 반복
   • i가 lcmA의 배수인지 확인 (i % lcmA === 0)
   • gcdB의 약수인지 확인 (gcdB % i === 0)
   • 조건을 만족하면 count++ 증가

---

🔹 예제 실행

입력

      
      
      
    
let a = [2, 4];
let b = [16, 32, 96];

console.log(getTotalX(a, b));

출력

 

      
      
      
    
3

과정

1. LCM(2, 4) = 4
2. GCD(16, 32, 96) = 16
3. 4, 8, 16이 조건을 만족 → 총 3개

---

🔹 시간 복잡도

• LCM과 GCD 계산 → O(N log M)
• LCM에서 GCD까지 숫자 탐색 → O(M / LCM)
• 전체적으로 O(N log M + M / LCM)
  (보통 N과 M이 크지 않으므로 충분히 빠름)

---

 😊