[C++] 최대공약수와 최소공배수 - 구현

기존 나의 풀이

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

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    int comp; // 숫자 교환
    if (n > m) {
        comp = n;
        n = m;
        m = comp;
    } // (n, m) 형태는 n <= m 형태가 될 것
    
    // 최대공약수
    if (m % n == 0) {
        answer.push_back((int)n);
    } else {
        answer.push_back((int)1);
    }
    
    // 최소공배수
    if (m % n == 0) {
        answer.push_back((int)m);
    } else {
        answer.push_back((int)(n * m));
    }
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] << " ";
    }
    return answer;
}

• 코드 분석: 로직상의 틀린 부분은 없었다. 다만, 제출 시 18.8%의 낮은 정확도를 보였고, 테스트 케이스를 추가했을때 [1000000 999999] 를 원하는 기댓값으로 처리하지 못하면서 Overflow가 발생하고 있었다.
• 이를 해결하기 위해 solution 함수와 answer 벡터를 long long int 형태로 선언했으나 이러면 출력 값에 모두 .0이 붙어 정수로 출력되지 않아 100% 오답이 발생했다.
• 반대로 int로 선언하고 m*n에서만 long long int 형으로 형변환을 시도했을때 역시도 원하는 값이 출력되지 않아 고민에 빠졌다.
• 로직의 문제도 없고, 형변환 시에도 해결되지 않아서 해설을 보았다.

정답 코드

#include <string>
#include <vector>
#define MIN(a,b) ((a<b)?a:b)

using namespace std;

// 최대공약수 (Greatest common divisor) 구하기: b = 0이 될 때까지의 재귀 함수 구조로 구현됨
int gcd(int a, int b){
    
    if(b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    // gcd 함수에 의해 리턴된 값이 num에 저장
    int num = gcd(n, m);
    
    // num을 가장 먼저 저장: 최대공약수
    answer.push_back(num);
    
    // 입력값인 n과 m의 곱을 num으로 나누어 최소공배수 결정
    answer.push_back(n * m / num);
    
    return answer;
}

• 궁금증:

• 기존에 내가 추가한 테스트 케이스로 [1000000 999999]를 넣었으나 기댓값인 [1 999999000000]가 나오지 않고 [1,-728379968]로 나오며 오답 처리되었고, [1000000, 1000000]에도 [1000000,-727] 이라는 오답을 출력한다.
  문제에서 주어진 자연수의 범위를 지키면서 테스트 케이스로 추가했는데 왜 제출 시 정답 처리가 되고, 내가 추가한 테스트 케이스에는 오답으로 내는걸까?

• 코드 분석: 최대공약수를 구하는 함수를 재귀 함수 형태로 구현했고, 내가 했던 방식처럼 a < b 형태가 되도록 값을 교환하는 코드로 짜여져 있다. a, b를 입력 매개 변수로 gcd 함수에 넣었을때 b가 0이 될 때까지 나머지를 리턴해가며 반복되는 형태로 재귀함수가 구현되었다. 이를 바탕으로 도출된 최대공약수를 num에 저장하고 입력 매개 변수의 곱을 num으로 나누면서 최소공배수가 도출된다.