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

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12953

문제 설명

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

제한 사항
 - arr은 길이 1이상, 15이하인 배열입니다.
 - arr의 원소는 100 이하인 자연수입니다.

문제 이해

- 처음에는 지수를 활용한 풀이로 풀었다.

참고) https://mathbang.net/204#gsc.tab=0

그런데, 코딩으로 풀이할 때는 별로 좋지 못한 접근인 것 같아 다른 방법을 찾아 보았는데, 역시나 깔끔한 풀이가 있었다.

최대공약수를 활용해 최소공배수를 구하는 방법이 있었다.

문제풀이

풀이 1) 지수를 이용한 풀이

# 약수와 그에 대한 지수를 return하는 함수이다.
# 1. arr안에 있는 수들중 최대값을 length로 하는 리스트를 만든다.
# 2. 약수와 약수의 지수를 구한다.
# 3. y_list에 약수가 없으면, 그 수는 소수이므로 n에 1을 넣는다.
def get_y(n, max_num):
    #약수 리스트
    y_list = [0 for _ in range(max_num)]
    
    if n < 4:
        y_list[n] = 1
        return y_list
    
    for i in range(2, n//2 + 1):
        k = 0
        while n % i == 0:
            n = n//i
            k += 1
        if k > 0:
            y_list[i] = k
    if max(y_list) == 0:
        y_list[n] = 1
    return y_list
            

def solution(arr):
    answer = 1
    y_arr = []
    
    for num in arr:
        y_arr.append(get_y(num, max(arr) + 1))
    
    # 위에서 만든 약수 리스트에서, 약수별로 제일 큰 지수를 골라 아래 수식을 적용시킨다.
    for i, li in enumerate(list(map(list, zip(*y_arr)))):
        if i == 0:
            pass
        answer *= i ** max(li)
    
    return answer

시간복잡도

처음 for문에서 O(len(arr))

두번째 for문에서는 O(max(arr)) # 주어진 숫자의 최대값

   get_y함수에서는 약 1/2 O(n), 이지만 최대 1/2 O(max(arr))이 된다.

get_y함수는 두번째 for문안에서 돌리니까

O(len(arr)) + O(max(arr)) * 1/2 O(max(arr))이 되고, arr은 최대 15, max(arr)은 최대 100이 되므로, 최악의 경우에 max(arr) 을 N이라고 하면

O(N**2) 가 된다.

 

풀이 2) 최대공약수를 이용한 풀이

최대공약수 및 최소공배수에 대한 이해도가 있다면, 나올 수 있는 풀이라고 생각한다. 나는 까먹어서 이 풀이를 생각해 내지 못했음.

# 두 수의 최대공약수를 구하는 함수. 재귀함수이다.
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

'''
이 코드에서는 유클리드 알고리즘(Euclidean algorithm)을 사용하여 최대공약수를 구한다. 
유클리드 알고리즘은 두 수 a, b (a > b)가 있을 때, 
a를 b로 나눈 나머지를 r이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 원리를 이용.
이를 반복하여 나머지가 0이 될 때까지 구하면, 최대공약수를 구할 수 있다.
'''

def nlcm(num):
    temp = 1
    for i in range(len(num)):
        temp = (num[i] * temp) / (gcd(num[i], temp))
    return temp

최소공배수는 다음 성질을 이용했다.

https://namu.wiki/w/%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

시간복잡도

- for문이 하나밖에 없으므로 O(len(num))이 된다. 위에 풀이보다 훨씬 효율적인 방법이라고 할 수 있다.

리뷰

- 최대공약수와 최소공배수의 성질을 까먹어서 좀 헤맸던 문제이다. 그래도 어렵게 진행한 풀이를 코드로 구현할 수 있었다는 것에 의의를 둔다.