[프로그래머스][C++] N개의 최소공배수

N개의 최소공배수

문제 링크

N개의 최소공배수

분석

arr배열에 들어있는 원소들의 최소공배수를 구해야합니다.

예를 들어 [2,6,8,14]의 경우 다음과 같은 순서로 최소공배수를 구합니다.

1. [2, 6]의 최소공배수인 $6$을 구합니다.
2. [2, 6]의 최소공배수인 $6$과 [8]의 최소공배수 $24$를 구합니다.
3. [2, 6, 8]의 최소공배수인 $24$와 [14]의 최소공배수 $168$을 구합니다.

풀이

#include <vector>
#include <numeric>

using namespace std;

int solution(vector<int> arr) {
    int answer = arr[0];
    
    // arr을 순회하는 반복문
    for (int i = 1; i < arr.size(); ++i)
    {
        // 최소공배수를 구하는 연산
        answer = answer * arr[i] / gcd(answer, arr[i]);
    }
    
    return answer;
}

반복문을 통해 원소를 하나씩 접근해 최소공배수를 구합니다.

성능 요약

시간 복잡도는 $O(n \ log \ m)$입니다.

• arr을 순회하는 반복문 $O(n)$
• gcd함수의 시간 복잡도 $O(log \ m)$
• $O(n \ log \ m)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 4.14MB)
테스트 2 〉 통과 (0.01ms, 4.23MB)
테스트 3 〉 통과 (0.01ms, 4.13MB)
테스트 4 〉 통과 (0.01ms, 4.16MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 3.64MB)
테스트 8 〉 통과 (0.01ms, 4.15MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 4.21MB)