[프로그래머스/C++ 문제 풀이] Lv. 2 - N개의 최소 공배수

문제 설명

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

제한 사항

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

입출력 예

---

문제 풀이

이번 문제는 N개의 수의 최소 공배수를 구하는 문제입니다.

 

저의 경우 N개의 수를 모두 소인수분해 하여 모든 값들 중 지수의 값이 가장 큰 값들만을 곱하는 방식으로 문제를 해결하게 되었습니다.

 

예를 들어, 2 6 8 14의 최소 공배수를 구하기 위해 소인수 분해를 하고 가장 지수가 큰 값들을 고르면 다음과 같습니다.

  2 : 2^1

  6 : 2^1 * 3^1

  8 : 2^3

14 : 2^1 * 7^1

 

즉, 2^3 * 3^1 * 7^1 = 168이 되는 것을 확인할 수 있습니다.

 

이번 문제에서 시간이 오래 걸렸던 이유는 전달받은 arr에 중복된 수가 있는 경우를 체크하지 않았기 때문입니다.

 

저의 경우 2중 배열을 통해 숫자 N의 약수들을 저장했는데, arr이 4, 4와 같이 같은 값이 나오는 경우 같은 위치에 중복된 값이 들어가게 되어 약수 2가 4번 사용된 것으로 체크되며 이를 확인하지 못해 많은 시간을 사용했습니다.

 

문제를 전부 풀고 최소 공배수를 구하는 방법에 대해 찾아본 결과 숫자 A와 B의 최소 공배수는 (A * B) / (A와 B의 최대공약수) 인 것을 알게 되었으며, 처음으로 최대 공약수를 구하는 "유클리드호제법"에 대해 알게 되었습니다.

정답 코드

풀이 시간 : 40m 31s

#include <string>
#include <vector>
#include <cmath>
#include <set>

using namespace std;

int NumCnt[101][101];

int solution(vector<int> arr) {
    int answer = 1;
    
    set<int> s;
    for (int i = 0; i < arr.size(); i++)
    {
        s.insert(arr[i]);
    }
    
    // 2 6 8 14의 경우 소인수분해를 하면
    // 2 : 2
    // 6 : 2 * 3
    // 8 : 2 * 2 * 2
    // 14 : 2 * 7
    
    // 소인수 분해 결과 지수가 가장 큰 수와 중복되지 않은 모든 수의 곱을 계산해보면?
    // -> 2 * 2 * 2 * 3 * 7 = 168
    
    for (int i : s)
    {
        // arr[i]번째 소인수분해 하기
        int n = 2;
        int tempNum = i;
        
        while (true)
        {
            if (n > tempNum) break;
            
            if (tempNum % n == 0)
            {
                NumCnt[i][n] += 1;
                tempNum /= n;
            }
            else
            {
                n++;
            }
        }
    }
    
    // 최소 공배수 구하기
    for (int i = 1; i <= 100; i++)
    {
        int mxNum = 0;
        
        for (int j = 1; j <= 100; j++)
        {
            mxNum = max(mxNum, NumCnt[j][i]);
        }
        answer *= pow(i, mxNum);
    }
    
    
    return answer;
}