프로그래머스) N개의 최소공배수 c++ 풀이

문제

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

코딩테스트 연습 - N개의 최소공배수

 

주어진 숫자들의 최소공배수(모든 수들의 배수이나 가장 작은 수)를 구하는 문제이다.

 

내 풀이

최소공배수가 될 수 있는 숫자(Now)를 증가시키면서, 주어진 arr 내의 모든 요소들이 Now의 약수인지 (나눴을 때 0이 되는지) 확인했다.

 

숫자(Now)를 증가시키는 방법은, 가장 큰 수를 기점으로 2배, 3배, 4배 ... 시키는 방식을 선택했다.

 

가장 큰 수를 증가시켜야 다른 숫자보다 빨리 답에 도달할 수 있고 연산을 줄일 수 있다.

 

1. arr를 정렬한다.

2. 가장 뒤에 있는 숫자를 알아낸다. (Last)

3. Now(증가시키며 최소공배수인지 확인할 수)를 Last로 두고, Last씩 증가시킨다.

3 - 1. 그 안에서 arr 의 모든 요소들이 Now의 약수인지 확인한다. (Now가 모든 요소들의 배수인지 확인한다.)

3 - 2. 최소공배수를 찾으면 return을 통해 while문을 나온다.

 

내 코드

 

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

using namespace std;

int solution(vector<int> arr) {
    int answer = 0;
    int Last;
    int Now;
    bool check;
    
    sort(arr.begin(), arr.end());
    Last = arr.back();
    Now = Last;
    
    while (1)
    {
        check = 1;
        for (auto & i : arr)
            if (Now % i != 0)
            {
                check = 0;
                break;
            }
        if (check)
            return Now;
        Now += Last;
    }
}

 

 

*주의할 점 : Now를 가장 뒤에 있는 수만큼(Last)씩 증가시키지 않고, Now += Now 라고 하지 않기

 

 

다른 사람의 풀이

앞에서 부터 순차적으로 최소공배수를 구해가는 풀이가 있었다.

a 와 b 의 최소공배수는 a * b / 최대공약수 와 같다.

 

arr[i] 와 arr[i + 1]의 gcd(최대공약수)를 구하고, arr[i] * arr[i + 1] 에 나눠주며 경신해가는 풀이가 인상깊었다.

최대 공약수를 구하는 코드는

 

long long gcd(long long a, long long b)
{
    long long c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}