Skip to main content

[Java] 12953 N개의 최소공배수

📝 N개의 최소공배수

1. 문제 요약

  • 배열 arr 요소들의 최소공배수 구하기

2. 정답코드

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0];
        for (int i = 1; i < arr.length; i++) {
            answer = lcm(answer, arr[i]);
        }
        return answer;
    }
    
    // 최대공약수
    public static int gcd(int a, int b) {
        // a % b를 반복해서 나머지가 0이 될 때의 a가 최대공약수
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp; 
        }
        return a;
    }
    
    // 최소공배수
    public static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
}

3. 설명

최소공배수 구하려면 유클리드 호제법으로 먼저 최소 공배수를 구하고, a*b/최소공배수로 나눠서 최대공약수를 구할 수 있다.

  1. answer 을 배열 첫번째 요소로 초기화
  2. arr배열을 index 1번부터 순회하며 answer, arr[i]의 최소공배수를 구하고
  3. 구한 값으로 answer을 업데이트
  4. answer 리턴

4. 오답 / 어려웠던 점

  • ​처음에 배열 for문 범위가 헷갈렸다. arr[i], arr[i + 1]이랑 비교하며 lcm 구하는 로직을 짰는데
  • 이렇게 하면전체 배열에 대한 최소공배수가 아니라 마지막 두 수의 최소공배수만 구하게 된다.
  • 처음에 쓴 코드는 아래와 같다.
for (int i = 0; i < arr.length - 1; i++) {
    lcm(arr[i], arr[i + 1]); // 결과를 저장 안 함
}
  • 결과도 answer에 반영하지 않으니까, 마지막에 answer는 여전히 0이거나 잘못된 값이 나오게 된다.
  • 배열 전체의 최소공배수를 구할 때는 누적해서 LCM을 갱신해줘야 한다.
  • 처음엔 answer = arr[0]으로 시작하고, 그다음부터는 answer = lcm(answer, arr[i]) 이렇게 계속 업데이트 하는 방법으로 수정했다.



Back to top