TIL - algorithm - 최소공배수

문제 설명

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

제한 사항

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

입출력 예제

arr	result
[2,6,8,14]	168
[1,2,3]	6

풀이

• 처음 풀이법으로 생각한 것은 배열 arr 안의 요소를 몫이 서로소가 될 때까지 1이 아닌 공약수로 나눠서, 공약수와 남은 몫 전체를 곱하는 방식이었다.(초등학교 수학 시간에 배웠던 지식을 토대로 생각한 것...) 하지만 공약수를 일일이 찾고, 나누는 로직을 코드로 구현하기에 굉장히 복잡한 것 같아 다른 방식으로 접근했다.

• 배열 안의 숫자 중 하나를 기준으로 정하고, 해당 숫자의 배수를 작은 수부터 차례대로 순회하면서, 배열 안의 모든 숫자로 나눠지는 수를 찾는 것이다. while loop로 순회를 하여, 가장 먼저 구한 공배수가 최소 공배수가 된다. 공배수를 구하는 조건은, 배열 안의 모든 요소로 나눠서 나머지가 0이 되는지 확인하는 것이다.

• 기준이 되는 숫자는 배열의 요소 중 최댓값으로 하는 것이 효율적이다.(상대적으로 적은 횟수를 순회하면서 최소 공배수를 찾을 수 있으므로)

def solution(arr):
    max_num = max(arr)
    answer  = max_num

    while True:
        is_multiple_true = 0
        for n in arr:
            if answer % n == 0:
                is_multiple_true += 1        
        if is_multiple_true == len(arr):
            break
        answer += max_num
           
    return answer

reviews

• while 무한루프(while True:)는 break문으로 특정 조건에서 반복을 중단시킬 수 있다. 무한루프라고 해서 무조건 사용을 지양할 필요는 없다. 적절히 활용하면 좋은 도구가 된다.