[프로그래머스 3단계] 알고리즘 28. N개의 최소 공배수

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 28. N개의 최소 공배수

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

#include<iostream>

#include<vector>

using namespace std;

long long nlcm(vector<int> num)

{

  long long answer = 0;

  return 0;

}

int main()

{

  vector<int> test{2,6,8,14};

  // 아래는 테스트로 출력해 보기 위한 코드입니다.

  cout << nlcm(test);

}

풀이:

이 문제의 답은 의외로 쉽게 풀 수 있다. 이미 이전에 최소공배수와 최대공약수를 찾는 방법에 대해 설명한 적이 있다. 그 문제를 그대로 이용할 것이다. 유클리드 알고리즘을 이용하여 얻는 최대 공약수 gcd와 a, b, gcd(a,b)를 이용하여 얻는 최소 공배수 lcm은 함수로 다음과 같이 작성할 수 있다.

long long gcd(long long a, long long b){

return (b == 0) ? a : gcd(b, a % b);

}

long long lcm(long long a, long long b){

 return a * b / gcd(a, b);

}

그렇다면 이제 벡터에 모여 있는 수들의 최소 공배수는 어떻게 구할까? 내가 생각해낸 알고리즘은 다음과 같다.

1. 먼저, 벡터들의 최소 공배수를 저장 시킬 변수 answer를 만든다.
   
2. 먼저 벡터의 첫번째 수를 꺼내어서 answer에 저장한다. (여기서 꺼내어 저장한다는 의미는 꺼낸 수는 벡터에서 삭제된다는 뜻이다.)
   
3. 그 다음 수부터는 벡터가 빌 때까지 꺼낸 후 answer와 최소 공배수를 구하여 answer에 누적시킨다. 

생각보다 어렵지 않다. 오히려 벡터를 큐로 생각할 줄 알면 쉽게 해결할 수 있다. 이제 코드를 보인 후 마무리 하겠다.

long long nlcm(vector<int> num)

{

  long long answer = num.back(); //1 + 2 결과를 누적시킬 변수 answer 선언과 함께 벡터의 첫 수를 꺼내어 초기화 시킨다.

num.pop_back(); //벡터의 수 삭제

while(num.size() > 0){ //벡터가 빌 때까지

answer = lcm(answer, num.back()); //벡터의 수를 꺼내어 asnswer와 최소 공배수를 구한 후 누적

num.pop_back(); //그 수 삭제

}

  

  return answer;

}

마무리하기 전에 이 문제는 더 개선할 여지가 남아있다. 나같은 경우에는 데이터가 소비되었다라는 것을 생각해두기 위해서 삭제 연산을 하였으나 굳이 벡터가 저장할 수들을 삭제할 이유가 있을까? 문제에서 벡터에서 사용한 원소는 버려진다 라는 명시가 없기 때문에 이는 의미 없는 연산에 불과하다. 그냥 벡터를 순회하면 쉽게 해결할 수 있다. 다음과 같이 말이다.

long long nlcm2(vector<int> num)

{

  long long answer = 1;   //1과 N의 최소 공배수는 N이다. 즉 누적시킬 변수로써 사용할 수 있다.

for (int N : num)

answer = lcm(answer, N);

  return answer;

}

이로써 3단계의 첫 문제를 풀어 보았다. 막 엄청 어렵지는 않았다. 3단계부터는 C++, Java, Python, JS로 풀 수 있기 때문에 되도록이면 C++로 해결을 보려 한다.