[Java] 프로그래머스 - N개의 최소공배수

배열에 담긴 여러 숫자의 최소공배수를 구하는 문제.

 

1. 문제 유형

수학, 구현

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 배열의 0번 인덱스와 1번 인덱스의 최소공배수를 구한 뒤 그 결과를 `currentNum`에 저장하고 다음 숫자와 다시 최소공배수를 구하려고 했다.

오답 원인: 두 수의 최소공배수를 찾는 내부 반복 조건이 잘못되었다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 두 수 a, b의 최소공배수는 a의 배수 중에서 b로 나누어떨어지는 가장 작은 수다.

풀이 아이디어:

1. currentNum에 배열의 첫 번째 값을 저장한다.
2. 다음 숫자 nextNum을 하나씩 꺼낸다.
3. currentNum의 배수를 증가시키며 nextNum으로 나누어떨어지는 값을 찾는다.
4. 찾은 값을 다시 currentNum에 저장한다.
5. 배열 끝까지 반복하면 currentNum이 N개의 최소공배수다.

4. 구현 코드

class Solution {
    public int solution(int[] arr) {
        int currentNum = arr[0];

        for (int i = 1; i < arr.length; i++) {
            int nextNum = arr[i];
            int candidate = currentNum;

            while (candidate % nextNum != 0) {
                candidate += currentNum;
            }

            currentNum = candidate;
        }

        return currentNum;
    }
}

시간 복잡도: O(N × M) / 공간 복잡도: O(1)

---

 

인사이트

• N개의 최소공배수는 한 번에 구하려고 하지 말고, 두 수씩 누적해서 구하면 된다.
• 최소공배수를 직접 탐색할 때는 * 2가 아니라 기존 수를 계속 더해서 배수를 확인해야 한다.
• 반복문의 조건은 “두 수가 같을 때”가 아니라 “현재 후보가 다음 숫자로 나누어떨어질 때까지”가 되어야 한다

 

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/12953