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

문제 설명

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

---

 

 

 

 

 

 

제한 사항

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

---

 

 

 

 

 

 

풀이

문제는 정말 간단하다.

n개의 수가 주어지면 n개의 최소공배수를 구하면 된다.

풀이법은 두 수의 최소공배수를 구하는 문제를 확장하면 되는 것이다.

두 수의 최소공배수를 구하는 법은 다음과 같다.

a, b라는 숫자가 있을 때, a와 b를 각각 소인수 분해한다.

소인수 분해하여 나온 수들을 모두 곱하면 되는데 겹치는 수는 한 번만 추가해야 한다.

예를 들어, a: {2, 2, 3}, b: {2, 3, 7}로 소인수 분해가 되었다면, 최소공배수는 겹치는 {2, 3}을 한 번만 추가하여 만든

{2, 2, 3, 7}을 모두 곱한 84가 된다.

 

이런 원리를 이용하여 여러 수로 확장하면 문제를 풀 수 있다.

위와 같은 상황에서 소인수들의 개수를 카운트해야 되기 때문에 map을 이용하였다.

소인수 분해하여 얻은 수들이 map에 저장되어있는 수보다 적다면 추가할 필요 없이 진행하고 그렇지 않다면 차이만큼 추가한다.

for(auto [num, cnt] : Current)
{
    if(Prime[num] < cnt)
    {
        Prime[num] += (cnt - Prime[num]);
    }
}

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <cmath>

using namespace std;

void Div(int n, map<int, int>& Prime)
{
    if(n == 1) return;
    
    vector<int> temp;
    while(n > 1)
    {
        bool canDiv = false;
        for(int i = 2; i <= sqrt(n); i++)
        {
            if(n % i == 0)
            {
                temp.push_back(i);
                n /= i;
                
                canDiv = true;
                break;
            }
        }

        if(!canDiv)
        {
            temp.push_back(n);
            break;
        }
    }
    
    map<int,int> Current;
    for(auto num : temp)
    {
        Current[num]++;
    }
    
    for(auto [num, cnt] : Current)
    {
        if(Prime[num] < cnt)
        {
            Prime[num] += (cnt - Prime[num]);
        }
    }
}

int solution(vector<int> arr) {
    int answer = 1;
    
    map<int, int> Prime;
    
    for(int num : arr)
    {
        Div(num, Prime);
    }
    
    for(auto [num, cnt] : Prime)
    {
        answer *= pow(num,cnt);
    }
    
    return answer;
}

---