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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12953

풀이

풀이 1 - (런타임 에러)

1. 최소공배수의 함수를 만든다.
2. arr배열이 홀수인 경우에 마지막에 1을 추가한다.
3. arr의 길이가 2가 되기 까지 (인덱스, 인덱스+1)의 최소공배수를 구한다.
4. 최종적으로 남은 arr의 두수에 대한 최소공배수를 구한다.

def gcm(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return (a * b) // gcm(a, b)

def solution(arr):
    if len(arr)%2 ==1:
        arr.append(1)
        
    while len(arr) > 2:
        temp = []
        for i in range(0, len(arr), 2):
            temp.append(lcm(arr[i], arr[i + 1]))
        arr = temp

    return lcm(arr[0], arr[1])

풀이 2 - (성공)

풀이 1의 solution 함수에서 런타임 에러가 발생하는 이유는, arr의 길이가 홀수인 경우 배열에 1을 추가하여 짝수로 만드는데, 이로 인해 입력이 문제에서 주어진 제한 사항을 위배할 수 있기 때문이다. arr 배열의 길이가 15이하까지만 되지만 1을 더하는 순간 길이가 16이 될 수 있다.

이 문제를 해결하기 위해, 길이가 홀수 인지를 판별하는 조건을 while문 내에 넣어 처리하면 된다.

def gcm(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return (a * b) // gcm(a, b)

def solution(arr):
    
    while len(arr) > 2:
        temp = []
        for i in range(0, len(arr), 2):
            temp.append(lcm(arr[i], arr[i + 1]))
            if len(arr) % 2 == 1:
                arr.append(1)
        arr = temp

    return lcm(arr[0], arr[1])

풀이 3 - (성공)

풀이 2는 통과는 되지만 메모리를 비효율적으로 사용하게 된다. 풀이 2와 논리적 전개는 비슷하지만 조금 더 코드를 효율적으로 사용한다면 아래와 같다.

def gcd(a, b):
    return gcd(b, a % b) if b else a

def lcm(a, b):
    return (a * b) // gcd(a, b)

def solution(arr):
    while len(arr) > 1:
        a, b = arr.pop(), arr.pop()
        arr.append(lcm(a, b))

    return arr[0]