[220914] Level_1 최대공약수와 최소공배수

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

프로그래머스

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

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    vector<int> nDivisor;//약수
    vector<int> mDivisor;
    vector<int> CommonDivisor; //공약수
    int greatestCommonDivisor = 0; //최대공약수
    int leastCommonMultiple = 0; //최소공배수

    for (int i = 1; i < n+1; i++)
    {
        if (n % i == 0) nDivisor.push_back(i);
    }
    for (int i = 1; i < m+1; i++)
    {
        if (m % i == 0) mDivisor.push_back(i);
    }
    for (auto i : nDivisor)
    {
        if (find(mDivisor.begin(), mDivisor.end(), i) == mDivisor.end()) continue;
        else greatestCommonDivisor = i;
    }
    leastCommonMultiple = n / greatestCommonDivisor * m;
    answer.push_back(greatestCommonDivisor);
    answer.push_back(leastCommonMultiple);

    return answer;
}

int main(void) {
    vector<int> answer = solution(3, 12);
    for (auto i : answer)
        cout << i << endl;
    return 0;
}

 

개선점

  굳이 a의 약수, b의 약수를 각각 구해서 둘의 공통분모를 찾을 필요가 없다. 아래 코드를 보면 if문에 &&연산자를 이용해 둘다 나누어 떨어지는 것을 공약수로 정하였음을 알수있다. 그리고 공약수를 구해 최대값을 찾을 필요도 없다. 아래 코드를 보면 for문에서 i를 제일 큰값부터 시작해서 --시켜주고 있다. 이렇게 하면 발견된 공약수는 최대공약수가 되고 이를 이용해 최대공배수까지 구할 수 있으니 바로 break로 나가기만 하면 된다. 이 쉬운 문제 풀자고 algorithm헤더,함수와 for문과 vector를 남발하다니,, 반성하자!! 

#include <iostream>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    int temp = a;

  if(a > b){
    a = b;
    b = temp;
  }

    vector<int> answer;

    for(int i = a; i > 0; i--){
    if(((a%i) == 0) && ((b%i) == 0)){
      answer.push_back(i);
      answer.push_back((a*b)/i);
      break;
    }
  }
    return answer;
}

int main(void) {
    vector<int> answer = solution(3, 12);
    for (auto i : answer)
        cout << i << endl;
    return 0;
}