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

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

프로그래머스

문제 유형 : 수학

문제 난이도 : Level 2

 

문제 설명

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

 

제한 사항

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

 

풀이

배열을 순차적으로 탐색하며 최소공배수를 구해주면 된다. 처음 값을 0번째 인덱스의 값으로 하고, 계속 자기 자신을 최소공배수로 업데이트 시킨다.

 

코드

C++(정석적으로 gcd를 구해서 곱에다가 나누는 방식이 아닌, 값을 누적해가며 비교하는 식으로 구현해보았다. 실제 환경에서는 비추천)

#include <string>
#include <vector>

using namespace std;

int lcm(int a, int b) {
    int x = a;
    int y = b;
    while(x !=y){
        if(x > y) {
            y += b;
        } else {
            x += a;
        }
    }
    
    return x;
}

int solution(vector<int> arr) {
    int answer = arr[0];
    for(int i = 1; i < arr.size(); i++) {
        answer = lcm(answer, arr[i]);
    }
    return answer;
}

 

 

Python3

import math

def lcm(a, b):
    return (a*b)//math.gcd(a, b)

def solution(arr):
    answer = arr[0]
    for i in range(1, len(arr)):
        answer = lcm(answer, arr[i])
    return answer

 

Java

class Solution {
    int gcd(int a, int b) {
        if(b == 0) {
            return a;
        }
        return gcd(b, a%b);
    }
    
    int lcm(int a, int b) {
        return a*b/gcd(a,b);
    }
    
    public int solution(int[] arr) {
        int answer = arr[0];
        for(int i = 1; i < arr.length; i++) {
            answer = lcm(answer, arr[i]);
        }
        
        return answer;
    }
}

 

Swift

func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a
    }
    return gcd(b, a % b)
}

func lcm(_ a: Int, _ b: Int) -> Int {
    return a * b / gcd(a, b)
}

func solution(_ arr: [Int]) -> Int {
    var answer = arr[0]
    for i in 1..<arr.count {
        answer = lcm(answer, arr[i])
    }
    return answer
}