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

문제 풀이 정리

 

문제 설명

두 수의 최소공배수(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

코드

def gcd(a,b):
    if a < b:
        a,b = b,a
    while b > 0:
        temp = b
        b = a % b
        a = temp
    return a

def solution(arr):
    answer = 1
    
    num_list = list(arr)
    for i in range(1, len(num_list)):
        gcd_num = gcd(num_list[i-1], num_list[i])
        answer = num_list[i-1] * num_list[i] / gcd_num
        num_list[i] = answer
    
    return answer

 

문제 넋두리

 

일단 첫번째

머리속에 둥둥 떠다니지만 정확히 짤수 없었던 알고리즘이 GCD(최대 공약수) 알고리즘을 구글링해서 가져왔다는 점이 자존심 상한다. 

두번째

역시 반례 생각이 진짜 어렵고, 길게 느껴진다. 그래서 질문하기 탭으로 가서 참고했다.

 

문제 예시를 본다면 [2,6,8,16] 을 보고

'아 모든 숫자가 특정 최대 공약수를 공통으로 가져야 가장 큰 최소공배수가 나오겠군'

이라고 생각하고 풀었더니 바로 틀렸다고 나왔다.

 

그래서 본 힌트가 

1. [3, 4, 9, 16] -> 144

2. 두 숫자끼리 최대 공약수를 비교한뒤 최소 공배수를 만들고 그다음 숫자는 해당 공배수와 최대 공약수를 추출한다.

 

1번 힌트를 보고 '엥 숫자 4개 전부를 표현하는 공약수는 1밖에 없는데?' 하는 지점이 이상했지만 결과로 나온 숫자는 실제로 숫자 4개를 곱한것 보다 작았기 때문에 고민이 깊어졌다.

그리고 2번을 보고 나서야 이해가 되었다.

 

이해되면 그다음은 쉽기 때문에 통과!