[Level 0] 정수 배열의 최대 공약수

문제

정수 배열 A에는 0보다 큰 숫자가 N개 들어있다. 
N개의 모든 숫자를 아우르는 최대 공약수를 구하는 프로그램을 구현하라. 

 

입력 형식

• A : 자연수가 담긴 정수 배열 

 

출력 형식

• 최대 공약수를 정수로 반환

 

제약 사항

• 0 < A.length <= 1000
• 0 < A[i] <= 100

 

입출력 예시

• 예시 1
• 입력 : A = [6, 12, 4]
• 출력 : 2
• 설명 : 모든 세 숫자의 최대 공약수는 2이다.

 

 

---

내 풀이

function solution(A) {
    let array = [];
    for(let v of A){
        array.push(getGcb(v));
    }
    let result = array[0];
    for(let i = 1; i < array.length; i++){
        result = result.filter((v) => array[i].includes(v));
    }
    return Math.max(...result);
}

function getGcb(num){
    let arr = [];
    for(let i = 1; i <= Math.sqrt(num); i++){
      if(num % i === 0) arr.push(i);
    }
    return arr;
}

• 시간 복잡도 : O(n * sqrt(m))
• 설명 : 위 코드의 시간 복잡도는 O(n * sqrt(m))이다. 여기서 n은 배열 A의 길이이고, m은 배열 A의 원소 중 가장 큰 값이다. 함수 getGcb에서 num을 sqrt(num)까지의 수로 나누어 확인하므로 시간 복잡도는 O(sqrt(m))이다. 이 함수를 배열 A의 각 원소에 대해 호출하므로 전체 시간 복잡도는 O(n * sqrt(m))가 된다.
  
  시간 복잡도가 O(n * sqrt(m))인데, 여기서 n과 m의 범위가 어떻게 되는지에 따라 효율성을 판단할 수 있다. 만약 n과 m이 작은 값일 경우에는 위 코드가 효율적일 수 있다. 하지만 만약 n과 m이 매우 큰 값일 경우에는 시간 복잡도가 크기 때문에 성능이 저하될 수 있다.
  
  또한 getGcb 함수에서 각 원소에 대해 약수를 구하고 배열로 반환하는 부분도 개선이 가능하다. 예를 들어, 에라토스테네스의 체 알고리즘을 사용하여 소수를 구하는 방법을 활용하면 효율적인 소인수분해 방법을 구현할 수 있다. 따라서 개선된 알고리즘을 사용하면 시간 복잡도를 줄일 수 있다.
  
  

---

해결 방법

function getGcd(a, b) {
  return b === 0 ? a : getGcd(b, a % b);
}

function solution(A) {
  let result = A[0];
  for (let i = 1; i < A.length; i++) {
    result = getGcd(result, A[i]);
  }
  return result;
}

• 시간 복잡도 : O(N * log(min(a, b)))
• 설명 : 위 코드는 최대공약수를 구하는 유클리드 호제법을 이용하여 주어진 정수 배열 A의 모든 요소들의 최대공약수를 구하는 함수다.
  getGcd(a, b) 함수는 두 정수 a와 b의 최대공약수를 구하는 재귀 함수이다. 유클리드 호제법을 이용하여 구현되어 있다. 시간 복잡도는 O(log(min(a, b))) 입니다.
  solution(A) 함수는 배열 A의 모든 요소들의 최대공약수를 구하는 함수이다. 배열의 길이가 N이라고 할 때, getGcd 함수를 N-1번 호출하면서 최대공약수를 구하게 된다. 따라서 시간 복잡도는 O(N * log(min(a, b))) 이다.
  이 문제에서 배열의 크기가 최대 1000이기 때문에 이러한 시간 복잡도는 충분히 효율적이라 할 수 있다. 따라서 위 코드는 효율적인 구현이라고 판단할 수 있다.
• 느낌점 : 본인은 재귀함수 사용을 굉장히 못하는 편이다. 최대 공약수를 구하는 부분까지는 작성이 가능한데, 이 최대 공약수를 사용해서 공통된 가장 큰 수를 구하는 재귀함수 방법은 생각지도 못했다. 세상에는 정말 대단한 코드를 짤 수 있는 사람이 많은 것을 오늘도 느꼈다. 지금부터 재귀함수 연습을 많이 해야겠다.

 

---