문제 12953. N개의 최소공배수

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2  

 

문제 요약 설명

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

입력

• n개의 숫자를 담은 배열 arr

입력 제한

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

입력 예제

// input
[2,6,8,14]

// ans
168

 

풀이 방식

해당 문제를 푸는 방법은 여러가지 있지만 map자료구조를 좋아하는 한 명으로써, 이 문제 또한 map을 이용해 문제를 푼다. 우선 arr에 저장된 각 숫자(elem)를 순회한다. 각 elem은 elem까지 순회하며(에라토스테네스의 체를 쓰면 더 좋다) 약수의 개수를 map자료구조 m 에 저장한다. 모든 약수의 개수를 구했다면, total_m이라는 map 자료구조에 약수에 개수를 저장한다. 단, total_m에 저장되어 있는 값보다 항상 큰 값을 저장한다.(최소공배수이기 때문)

 

arr의 순회를 끝냈다면 map에 저장되어 있는 약수와 약수의 개수를 전부 곱하면 최소공배수가 나온다.

 

정답 코드 

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

using namespace std;

int solution(vector<int> arr) {
    long long answer = 1;
    
    map<int, int> total_m;
    
    for(int elem : arr){
        map<int, int> m;
        for(int n = 2; n <= elem;){
            if(elem % n == 0){
                elem /= n;
                m[n]++;
            }
            else{
                n++;
            }
        }
        
        for(auto it : m){
            //cout << it.first << " " << it.second << '\n';
            total_m[it.first] = max(total_m[it.first], it.second);
        }
    }
    
    // 최소 공배수 구해서 정답에 넣기
    for(auto it : total_m){       
        for(int i = 0; i < it.second; i++){
            answer *= it.first;
        }
    }
    
    return answer;
}

 

더 좋은 코드?

이번 문제는 유클리드 호제법을 통해 구하는, 이미 구하는 방법이 정해져있는 문제이다. 아래 링크를 보면 알 수 있듯, 최대 공약수와 최소 공배수를 GCD, LCM이라고 부르며 매우 짧은 코드로 GCD, LCM을 구하는 모습을 볼 수 있다. 알아두면 엄청나게 코드가 줄어들테니 기억해두면 꽤 유용하게 활용할 수 있을 것이다.

참고

https://heoseongh.github.io/algorithm/Euclidean/

최대 공약수(GCD) 알고리즘 - 유클리드 호제법

 

유클리드 호제법 원리

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

유클리드 호제법 (개념 이해하기) | 모듈로 연산 | Khan Academy