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

문제

원래의 최소공배수에서 정의를 확장하여

n개의 수의 최소공배수는 n개의 수들의 배수 중 공통이 되는 가장 작은 수가 된다고 하자.

 

n개의 숫자가 담긴 배열 arr이 매개변수로 주어질 때 이 수들의 최소공배수를 반환하는 함수를 만들어야 한다.

 

 

제한조건

1. arr은 길이 1이상, 15이하인 배열이다.

2. arr의 원소는 100이하인 자연수이다.

 

 

코드

from math import sqrt

def solution(arr):
    def factorization(n):
        factor = 2
        factors = []
        
        while (factor <= sqrt(n)):
            while (n % factor == 0):
                factors.append(factor)
                n //= factor
            factor += 1

        if n > 1:
            factors.append(n)
            
        return factors
    
    num_dict = {}
    for num in arr:
        for factor in factorization(num):
            count_factor = factorization(num).count(factor)
            try:
                if num_dict[factor] < count_factor:
                    num_dict[factor] = count_factor
            except:
                num_dict[factor] = 1
    
    answer = 1
    for key, value in num_dict.items():
        answer *= key**value

    return answer

 

 

설명

위 문제는 아래 순서로 풀게된다.

1. arr로 주어지는 각 수를 소인수분해해서, 소수들로 쪼갠다.

2. 등장하는 소수를 기록한다.

3. 소인수분해 했을 때 나온 소수 하나하나당 개수를 세서 가장 큰 값을 같이 기록한다.

ex) [2, 2, 2, 3, 5] -> {2: 3, 3: 1, 5: 1}

4. 기록한 소수들을 각각의 가장 큰 등장횟수로 제곱하여 이 수들을 곱해준다.

ex) {2: 3, 3: 2, 5: 1} -> answer = \(2^3 \times 3^2 \times 5^1\)

 

def factorization(n):
	factor = 2
	factors = []
        
	while (factor <= sqrt(n)):
		while (n % factor == 0):
			factors.append(factor)
			n //= factor
		factor += 1

	if n > 1:
		factors.append(n)

return factors

소인수분해 함수이다. n을 입력하면 n에 해당하는 소인수분해 결과가 리스트형태로 반환된다.

자세한 알고리즘은 링크참조

 

num_dict = {}

소인수분해한 결과들을 기록할 딕셔너리이다. key를 소수로, 등장 횟수를 value로 갖게할 것이다.

 

for num in arr:

arr에 들어있는 수들을 하나씩 꺼내어 반복한다.

 

for factor in factorization(num):
	count_factor = factorization(num).count(factor)

앞에서 꺼낸 수를 소인수분해한다.

소인수분해하여 나온 리스트에 들어있는 수들을 하나씩 꺼내어 반복한다.

현재 소인수(factor)의 개수를 세어 count_factor에 저장한다.

 

try:
	if num_dict[factor] < count_factor:
		num_dict[factor] = count_factor
except:
	num_dict[factor] = 1

num_dict에 factor라는 key가 없다면 except로 넘어가게 된다. 이 때는 num_dict에 factor를 key로 갖는 값을 기록한다.

num_dict에 factor를 key로 갖는 값이 있다면 그 값과 count_factor를 비교하여 큰 수를 num_dict[factor]에 기록한다.

 

answer = 1
for key, value in num_dict.items():
	answer *= key**value

반복문이 끝나면 num_dict에 최종적으로 원하는 값들이 기록되어 있다.

key, value를 꺼내어 설명에서 말한 방법으로 계산한다.