프로그래머스 N개의 최소공배수 코드 및 해설 (파이썬)

programmers.co.kr/learn/courses/30/lessons/12953

코딩테스트 연습 - N개의 최소공배수

 

💡 N개의 숫자를 소인수분해한 후 Counter를 이용해 합집합을 구하여 모두 곱했습니다. 

 

arr에 주어진 수를 소인수분해하기 위해 factorize와 이에 사용되는 isPrime 함수를 추가로 만들었습니다.

 

isPrime은 숫자를 입력으로 받고 이 숫자가 소수면 True, 아니면 False를 반환하는 함수입니다.

 

factorize 함수는 숫자를 입력으로 받고 이를 소인수분해한 결과를 list로 반환하는 함수입니다. 이때 제곱수가 입력된다면 특정 소수가 제곱된 개수만큼 결과에 포함되도록 했습니다. 이를 위해 while문을 통해 해당 소수로 나눌 수 있을 때까지 나누었고, 나머지가 0이 아니거나 몫이 1이 되면 while을 탈출하도록 했습니다.

예를 들어, 8이 입력되면 [2,2,2]를 반환하고 100이 입력되면 [2,2,5,5]가 반환됩니다. 

 

solution 함수에선 arr에 주어진 모든 숫자들을 소인수분해하고, Counter를 이용해 이 list들의 중복을 포함한 합집합을 구했습니다. 

예를 들어, [2,6,8,14]가 solution의 입력으로 주어졌다면 각각의 factorize 함수의 결과인 [2], [2,3], [2,2,2], [2,7] 의 중복을 포함한 합집합, 즉 [2,2,2,3,7]을 구하고자 합니다. 여기선 Counter를 사용했으므로 result엔 Counter = {2:3, 3:1, 7:1} 형태로 저장됩니다. (key는 소인수분해의 소수, value는 그 소수가 사용되는 빈도) 

 

마지막으로 이 합집합에 있는 소수들을 개수만큼 모두 곱해서 최종 답을 반환했습니다. 

앞선 예에서 result가 Counter = {2:3, 3:1, 7:1} 라면, 2는 3번, 2은 1번, 7은 1번 곱해야 최종 답을 구할 수 있습니다. 따라서 2**3 * 3**1 * 7**1 을 계산할 수 있도록 for 문을 사용합니다. 

 

import math 
from collections import Counter

# 소수 판별하기 
def isPrime(num):
    if num == 1:
        return False 
    
    if num == 2:
        return True 
    
    # 에라스토로스의 체
    for i in range(2, math.ceil(math.sqrt(num))+1):
        if num % i == 0:
            return False
    
    return True 

# 소인수분해하기 
# ex. 4 -> [2,2]
# ex. 14 -> [2,7]
def factorize(num):
    result = []
    
    # 그 자체로 소수거나 1이라면 자기 자신만 반환 
    if isPrime(num) or num == 1:
        return [num]
    
    for i in range(2, (num//2)+1):
        if num % i == 0 and isPrime(i):
            count = 1
            share = num // i 
            # 제곱수를 처리하기 위한 while문 
            while share != 1:
                if share % i != 0:
                    break
                share = share // i 
                count += 1 
            result += [i] * count 
    
    return result

# N개의 최소공배수 구하기 
def solution(arr):
    answer = 1 
    # 주어진 숫자를 소인수분해한 결과의 중복을 포함한 합집합 
    result = Counter()
    
    for num in arr:
        result |= Counter(factorize(num))
    
    # 소인수분해한 결과의 합집합을 곱해 최종 답을 계산
    for key in result:
        answer *= key ** result[key]
        
    return answer