[프로그래머스] N개의 최소공배수 - 파이썬(python)

프로그래머스

문제

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

제한사항

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

풀이 설계

• n개의 수의 최소공배수를 구하기 위해서 배열의 숫자를 소인수분해하여 각 소수의 최대 제곱 값을 구해야한다.
• arr의 원소는 100이하 이므로 소수의 개수를 세기 위한 배열을 설정한다. (이하 temp)
• for문을 통해 원소를 하나씩 소인수 분해 한다.
• while문을 사용하여 2부터 나누기 시작해서 num(원소)가 1이 되면 중단한다.
• 나눌 때 나머지가 남지 않는 경우 나누고 횟수를 카운트한다.
• temp배열에서 최대값을 갱신한다.
• for문이 종료된 후 temp배열이 0이 아닌 경우 해당 값을 인덱스의 제곱으로 사용하여 모두 곱한다.

코드

def solution(arr):
    answer = 1
    temp = [0]*101
    for num in arr:
        tm = 2
        cnt = 0
        while 1:
            if num == 1:
                break
            if num % tm == 0:
                cnt+=1
                num = num // tm
                temp[tm] = max(temp[tm], cnt)
            else:
                cnt = 0
                tm+=1
    for idx in range(1, 101):
        if temp[idx] != 0:
            answer *= idx**temp[idx]
    return answer

다른 코드

• math.gcd 함수(최대공약수를 구하는 함수)를 사용하는 방법
• (주의) 파이썬 3.9미만 버전에서는 gcd인수로 2개까지 허용된다. (프로그매머스는 3.9미만)
• 3.9이상 버전에서는 gcd함수의 인수로 여러개를 사용할 수 있다.
• 3.9이상 버전에서는 lcm이라는 최소공배수를 구하는 함수도 사용 가능하다.

import math

# 최소공배수 구하는 함수
def lcm(a,b):
    return a*b // math.gcd(a,b)

def solution(arr):
    answer = arr[0]
    for i in arr[1:]:
        answer = lcm(answer,i)
    return answer

유클리드 호제법

• 만약에 math 라이브러리를 사용할 수 없다면 유클리드 호제법을 사용하여 최대공약수를 구할 수 있다.

# 유클리드 호제법을 사용하여 최대공약수 구하기
def gcd(a,b):
    while b:
        r = a%b
        a,b = b,r
    return a

# 최소공배수 구하기
def lcm(a,b):
    return a*b // gcd(a,b)

def solution(arr):
    answer = arr[0]
    for i in arr[1:]:
        answer = lcm(answer,i)
    return answer

왼쪽부터 순서대로 순수 구현, math.gcd함수 사용, 유클리드 호제법 사용

후기

• 파이썬에서 내장함수나 라이브러리를 사용하는 것이 익숙하지 않아서 사용할 생각을 못해봤는데 확실히 코드가 짧아지고 읽기 쉬워지는 것 같다.
• 유클리드 호제법에 대한 이해가 필요할 것 같다.