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

 

 

 

처음 작성한 코드는 다음과 같다.

수마다 약수를 구해 구해진 약수들을 중복없이 모두 곱해 최소공배수를 구하려고 했으나 오류가 났다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(vector<int> arr) {
    int answer = 1;
    bool ans[101] = {0,};
    
    // 숫자마다 약수 구해서 배열ans에 저장
    for(int i=0; i<arr.size(); i++) {
        for (int j=1; j<=arr[i]; j++) {
            if (arr[i] % j == 0)
                ans[j] = 1;
	    }
    }
    
    //최소공배수 구하기
    for(int i=1; i<=100; i++) {
        if(ans[i] == 1)
            answer *= i;
    }
    
    return answer;
}

 

그냥 약수만 다 구해서 곱하면 되는 줄 알았지만 이렇게 하면 문제가 있었다.

예를 들어 8이 주어졌다면 이 수는 약수가 2밖에 없지만, 2만 1번 곱하면 8을 곱하는 건 아니게 된다.

최종 최소공배수가 8의 배수가 아닐 수도 있다는 것이다.

문제를 잘못 이해한 것 같다.

 

 

 

수정한 코드는 다음과 같다.

최소공배수를 구하는 공식을 구현하려 했다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int solution(vector<int> arr) {
    int answer = 1;
    
    sort(arr.begin(), arr.end());
    
    //최소공배수 구하기
    for(int i=1; i<=arr[arr.size()-1]; i++) {
        bool mul = true;
        
        for (int j=0; j<arr.size(); j++) {
            //나눠떨어지지 않는 수 i라면 pass
            if( arr[j]%i != 0 ) {
                mul = false;
                break;
            }
	    }
        
        //구한 약수 차례로 곱해줌, 최소공배수 계산해가기
        // arr의 숫자들 공통약수로 나눠주기
        if(mul == true) {
            answer *= i;
            for(int j=0; j<arr.size(); j++) 
                arr[j] = arr[j]/i;
            i = 0;
        }
    }
    
    //마지막에 더이상 나눠지지않고 남은 수들 다 곱해주기
    for(int j=0; j<arr.size(); j++)
        answer *= arr[j];
    
    return answer;
}

하지만 이번엔 시간 초과 오류가 생겼다.

중첩 for문을 사용한 것이 시간 복잡도에 영향을 미친 것 같았다.

 

 

 

다른 사람들의 풀이를 보니까 시간문제를 줄이기 위해 재귀함수와 최대공약수를 활용했다.

최소공배수를 구하는데 최소공약수와의 관계를 활용하여, 두 수의 최소공배수는 "(a * b) / (a,b의 최대공약수)"라는 식을 활용한 것이다.

(재귀함수는 최대공약수를 구하는 과정에서 간단하게 구현하기 위함이었다.)