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

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

 

TL;DR

• 주어진 문제 조건에 따라 구현(implementation)할 수 있는지
• 유클리드 호제법

문제 분석

1. n개의 숫자를 담은 배열 arr에 대해 이 수들의 최소 공배수를 반환하는 함수를 작성하라.

 

- 해결해야 하는 문제 조건에 대해서 말하고 있다.

- 최소공배수이기 때문에, 배열을 순회하며 최소공배수를 배열 내의 숫자 간의 최소공배수로 갱신하면 풀 수 있다.

입출력 형태

입출력 예시

 

- 숫자들이 저장된 arr이 입력으로 주어진다.

- 예시 1번을 확인해보면

    - 2와 6의 최소공배수는 6이다.

    - 6과 8의 최소공배수는 24이다.

    - 24와 14의 최소공배수는 168이다.

- 이와 같이 배열에서 두 수 간의 최소공배수를 구한 뒤 다음 원소들과 최소공배수로 갱신해나가면 문제를 해결할 수 있다.

풀이

def solution(arr):
    def euclid(big, small): # 1
        return small if big % small == 0 else euclid(small, big % small)
    
    if len(arr) == 1: # 2
        return arr[0]
    
    sorted_arr = sorted(arr) # 3
    answer, gcd = sorted_arr[0], 0
    for i in range(1, len(sorted_arr)): # 4
        gcd = euclid(answer, sorted_arr[i])
        answer = int(answer * sorted_arr[i] / gcd) # 5 

    return answer

 

- 1 : 최대공약수와 최소공배수를 구하는 방법은 유클리드 호제법을 사용하는 것이다.

    - 큰 수를 작은 수로 나눈다. 이 때 나누어 떨어지지 않는다면 큰 수를 큰 수와 작은 수로 나눈 나머지로 변경하고, 작은 수와 연산을 진행한다.

    - 나머지가 없을 때까지 위의 과정을 반복한다. 그렇게 하면 최대공약수를 얻을 수 있다.

    - 최소공배수는 두 수를 곱한 수를 최대공약수로 나눈 수이다.

    - 최대공약수를 구하는 함수를 작성하였다. 두 수가 나누어떨어질 때까지 재귀적으로 반복된다.

 

- 2 : 예외처리를 한다. 배열의 길이가 1일 때는 바로 원소를 반환하면 된다.

 

- 3 : 주어진 배열을 정렬한다. 작은 수부터 순차적으로 최소공배수를 구하는데 사용한다.

 

- 4 : 배열의 처음 원소를 제외한 다음 원소부터 배열을 순회하며 최소공배수를 갱신한다.

- 5 : 작성한 유클리드 호제법 함수를 사용해 최대공약수를 구하고, 최소공배수를 구해서 answer에 갱신시킨다.

- 최종적으로 모든 수에 대한 최소공배수를 구할 수 있고, 이를 반환한다.