[프로그래머스] - N개의 최소공배수(C++)

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

 

시작 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> arr) {
    int answer = 0;
    return answer;
}

 

나의 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 최대 공약수 구하는 gcd
int gcd(int x, int y)
{
    return x % y == 0 ? y : gcd(y, x % y);
}

// 최소 공배수 구하는 lcm 
int lcm(int x, int y)
{
    return x * y / gcd(x, y);
}

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

 

코드 분석

gcd와 lcm 함수를 만들어 사용합니다. gcd는 int형 x,y를 인자로 받아 삼항연산자를 통해 x를 y로 나눈 나머지가 0이면 y를 리턴하고 그게 아니라면 다시 gcd함수를 재귀적으로 리턴합니다. 이때 x자리에는 y를, y자리에는 x를 y로 나눈 나머지를 넣습니다. lcm은 마찬가지로 x,y를 인자로 받고 x와 y를 곱한 값을 gcd(x,y)로 나누값을 리턴합니다.

 

리턴할 answer 값을 배열로 바꾸고 1부터 반복문을 배열 사이즈까지 순회하여 answer에 lcm함수를 실행시킨 값을 넣습니다. lcm은 x자리에 answer를, y자리에 arr[i]값을 넣고 실행합니다. 마지막엔 answer값을 리턴합니다.

 

풀이 설명

이 문제에서 원하는 것은 간단하게 배열 안에 있는 수들의 최소공배수를 구하는 것입니다. 이 문제에서 우리는 이전에 공부했던 최대공약수와 최소공배수를 구하는 공식인 유클리드 호제법을 활용할 수 있습니다. 최대공약수는 gcd 함수를 통해서 구현하고, 최소공배수는 lcm 함수를 통해서 구현하여 최종적으로 배열 내 모든 수의 최소공배수를 answer에 담아 리턴하게 됩니다.

 

시간복잡도 : O(nlogm)

공간복잡도 : O(1)

 

실행결과

 

<NEXT>

이번에는 유클리드 호제법의 개념을 활용하는 정답률  70%의 "n개의 최소공배수" 문제를 풀어보았습니다. 다음에는 Summer/Winter Coding(~2018) 문제 중 하나인 "영어 끝말잇기" 문제를 풀어보도록 하겠습니다. 감사합니다.