[2025.02.20] N개의 최소공배수

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소 공배수는 14가 됩니다. 정의를 확장해서 n개의 수의 최소공배수는 n개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

 

 

제한사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

 

 

입출력 예

arr			result
[2, 6, 8, 14]			168
[1, 2, 3]			6
[2, 7, 14]			14

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> arr) {
    int answer = 1;
    
    int number=(*max_element(arr.begin(), arr.end()))+1; // 반복 횟수
    int count=0; // 나누어 떨어지는 값의 개수
    vector<int> divisors; // 공약수들
    
    // 공약수 구하기
    for(int divisor=2; divisor<number; divisor++)
    {
        count=0; // 초기화
        
        // divisor로 나누어 떨어지는 개수 구하기
        for(int i=0; i<arr.size(); i++)
        {
            if(arr[i]%divisor==0)
            {
                count++;
            }
        }
        
        // 공약수가 존재한다면
        if(count>1)
        {
            divisors.push_back(divisor);
            
            // arr 값 업데이트
            for(int i=0; i<arr.size(); i++)
            {
                if(arr[i]%divisor==0)
                {
                    arr[i]/=divisor;
                }
            }
            
            // 똑같은 divisor로 또 나누어 질 수도 있기 때문에
            divisor--;
        }
        
    }
    
    // 최소 공배수 구하기
    for(int num : arr)
    {
        answer*=num;
    }
    for(int num : divisors)
    {
        answer*=num;
    }
    
    
    return answer;
}

 

 

N개의 최소공배수를 구하는 것은 두 수의 최소공배수와 비슷하지만 다른점이 있다. 하지만 두 수의 최소공배수를 구하는 방법도 정확하게 기억이 나지 않아 예전에 풀었던 문제를 다시 찾아보았다.

https://iiblueblue.tistory.com/147

[2025.01.09] 최대공약수와 최소공배수

저번에 풀었던 이 문제를 다시 살펴보니 최소 공배수를 구하는 방법은 두 수의 공약수와 서로소 모두를 곱하는 것이었다.

그러니까 결국 2×3×5×7을 한 것이 최소 공배수라는 뜻이다.

 

그렇다면 N의 최소공배수는 어떻게 구할 수 있는지 설명하기 위해 숫자 3개를 준비했다. 그 특징을 명확히 보기 위해서는 직접 추가한 입출력 에제 3을 살펴보는 것이 좋겠다.

두 수의 최소공배수를 구하는 것과 다른 점이 있다면 세 개의 수가 모두 나누어 떨어지는 공약수가 아니어도 된다는 것이다. 2, 7, 14는 사실 세 수가 동시에 나눠지는 공약수는 없다. 2와 14는 2로 나누어 떨어지고 7과 14는 7로 나누어 떨어진다. N개의 수의 최소공배수를 구할 때는 세 수가 모두 나누어 떨어지지 않아도 나누어 떨어지는 수만 나누어 계산한다. 그리고 나누어 떨어지지 않는 수는 그대로 내려오게 된다. 위에서는 우선 2로 나누었다. 2로 나누어 떨어지지 않는 7은 7그대로 내려왔다. 그 상태에서 다시 보니 이번에는 7과 7이 7로 나누어 떨어지는 상황이다. 7로 나누어 주고 7로 나누어 떨어지지 않는 1은 그대로 내려온다. 이제 모두 1이 되었으니 공약수들과 서로소들을 모두 곱해주면 된다. 2×7×1×1×1=14가 바로 최소공배수이다.

 

이 과정을 그대로 코드로 구현하면 된다. 이전과 비슷하지만 이번에는 모든 수가 나누어 떨어지는 것을 보는 것이 아니라 최소 2개의 수만 나누어 떨어지면 된다. 그래서 나누어 떨어지는 값의 개수를 구하기 위해 count 변수를 선언해준다. 공약수를 구하기 위한 반복 횟수도 기존에는 최소값을 기준으로 하였지만 위의 예제처럼 2, 7, 14의 경우 최소값 2를 기준으로 하였다간 7로는 나누보지도 못하고 끝날 수 있다. 그래서 최댓값을 기준으로 해주었다. 마지막으로 이전처럼 공약수를 담을 vector인 divisors를 준비하였다.

 

2로 시작하여 반복문을 최댓값만큼 돌며 두 가지 일을 수행한다.

1. divisor로 나누어 떨어지는 수의 개수 구하기
2. 나누어 떨어지는 개수가 2이상이면 공약수가 존재하는 것으로 판단하고 처리하기

count값을 초기화해주고 for문을 이용해서 arr에 있는 모든 수를 divisor로 나머지 계산을 하여 그 중 나누어 떨어지는 수가 몇개인지 count를 업데이트하여 게산한다. 계산이 끝난 후 count를 확인하여 2개 이상이라면 공약수가 존재하는 것이므로 처리를 한다. divisor를 divisors에 저장하고 arr값을 업데이트한다. arr값은 나누어 떨어진다면 나누어 주고 그렇지 않다면 그냥 그대로 놔두도록 한다. 마지막으로 같은 수로 다시 나누어 떨어질 수도 있기 때문에 divisor를 -1해주어 같은 수로 한번 더 공약수가 될 수 있는지 검사하도록 한다.

 

반복문이 끝나고 마지막으로 arr에 있는 서로소들과 divisors에 있는 공약수들을 모두 곱해서 answer을 만든다.

 

 

오답 노트

처음에 입출력 예제 1, 2를  보고 두 수의 최소공배수를 구하는 방법과 같은 방법을 사용하면 N개의 수의 최소공배수도 구할 수 있을 것이라고 생각했다. 그래서 나누어 떨어지는 수를 count하지 않고 모든 수가 나누어 떨어질 때만 공약수를 저장하는 처리를 하였다. 결론적으로 입출력 예제 1과 2는 통과하였지만 실제 답을 제출하였을 때는 모든 테스트가 오답이 나왔다.

...
for(int divisor=2; divisor<number; divisor++)
{
    isDivisor=true;
    for(int i=0; i<arr.size(); i++)
    {
        if(arr[i]%divisor!=0)
        {
            isDivisor=false;
            break;
        }
    }

    if(isDivisor)
    {
        divisors.push_back(divisor);
        for(int i=0; i<arr.size(); i++)
        {
            arr[i]/=divisor;
        }
        divisor--;
    }

}
...

 

반복의 횟수를 arr의 최소값을 기준으로 하였다가 오답을 만났다. 새로 추가한 입출력 예제 3을 생각하니 최소값인 2로 반복횟수를 정하였을 때 7로 나눌 기회는 없다는 것을 깨달았다. 사실 가장 큰 수보다 하나 작은 수로 반복을 돌면 괜찮을 것 같다는 생각을 하긴 했지만 제한 사항에서 제시한 수를 보니 반복의 크기는 크게 의미있지 않을 것 같아 최대값으로 진행하였다.

 

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12953#

프로그래머스