[프로그래머스] 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 이하인 자연수입니다.

N개의 수의 최소공배수 = 최대공약수 * a * b * c * ... * n 이므로
N개의 수의 최대공약수를 구하고 arr안의 모든 요소를 곱한 뒤 최대공약수**(n-1)로 나눠주면 될 듯
제한 조건에서 100이하인 자연수니깐 다 나눌 필요없이 100 이하 소수로만 나눠서 최대 공약수 판단하면 될 듯

---

풀이

 

로직

1 ~ 100까지 소수를 먼저 찾고

> 주어진 arr에서 각 수를 인수분해하고 각 인수가 높은 것만 모아서 곱하면 최소 공배수

> 또는 math의 gcd를 사용해 풀기

 

초기 코드

# 초기 코드
def is_prime(num):
    for i in range(2, int(num**(0.5))+1):
        if not num % i: return False
    return True
    
def solution(arr):
    prime_counts = {}
    for i in range(2,101):
        if is_prime(i): prime_counts[i]=0
    divisor = []
    for num in arr:
        if num == 1: continue
        num_dict = {}
        for prime in prime_counts.keys():
            prime = int(prime)
            while num % prime == 0:
                num_dict[prime] = num_dict.get(prime,0) + 1
                num = num // prime
        divisor.append(num_dict)
    for divisor_dict in divisor:
        for key,value in divisor_dict.items():
            prime_counts[key] = max(prime_counts[key], value)
    answer = 1
    for key, value in prime_counts.items():
        answer *= key**value
    return answer
# 0.18ms

 

초기 코드는 러프하게 짜기때문에 불필요한 로직이나 알기 힘든 변수명들이 보인다.

 

특히 num_dict 에 각 인수의 갯수를 넣고 divisor 에 num_dict를 넣고

다시 for를 돌려서 prime_counts에 넣는부분을 바로 prime_counts에 넣으면 될 듯.

 

1차 수정 : 가독성 및 로직 개선

# 1차 수정 : 가독성 및 로직 개선
def is_prime(num):
    for i in range(2, int(num**(0.5))+1):
        if not num % i: return False
    return True

def solution(arr):
    answer = 1
    primes = [i for i in range(2, 101) if is_prime(i)]
    prime_counts = {prime: 0 for prime in primes}
    for num in arr:
        if num == 1: continue
        for prime in prime_counts.keys():
            if num < prime: break
            count = 0
            while num % prime == 0:
                count += 1
                num = num // prime
            prime_counts[prime] = max(prime_counts[prime], count)
    for key, value in prime_counts.items():
        answer *= key**value
    return answer
# 0.10ms

 

불필요한 for문을 줄이고, for 문을 일찍 끝내기 위해 break를 추가했다.

 

근데 이런 수학적 문제들은 math를 가져오면 쉽게 풀 수 있다.

두 수(x, y)의 최소공배수(Least Common Multiple, LCM)는

두 수를 서로 곱하고 두 수의 최대공약수(Greatest Common Divisor)를 나누면 나온다.

그럼 여러 수의 최소공배수는? 두 수의 LCM을 구하고 그 LCM과 한 수의 LCM을 구하고..를 반복하면 된다.

functools의 reduce를 이용하면 이 과정을 쉽게 할 수 있다.

 

2차 수정 : gcd, reduce를 사용해 풀기

# 2차 수정 : gcd, reduce 사용해 풀기
import math
from functools import reduce
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
def solution(numbers):
    return reduce(lcm, numbers)
# 0.01ms

 

시간도 엄청 단축된다. 근데 항상 고민이 되는 부분이 'import를 해서 문제를 푸는게 맞을까?' 하는 것이다.

될 수 있으면 import 없이 코드를 구현하는게 맞다고 생각하지만,

itertools의 permutations나 combinations 같은건 직접 구현하기 너무 귀찮다..

 

그냥 import 없이 풀고 하고 풀고 두번 풀면 해결 !