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

문제주소 :programmers.co.kr/learn/courses/30/lessons/12953

코딩테스트 연습 - 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

 

<풀이법>

▒ 한줄 개념: 최소공배수 ▒ 

보통 최소공배수라 함은 2개의 숫자에 대한 최소공배수를 구하는데, 이 문제는 그 개념을 확장시켜 n개의 수에 대한 최소공배수를 구하는 문제입니다.

 

1. arr정렬 후 이미 다른 원소의 약수인 원소들을 지움(0으로 만듬)
2. 현재 남아있는 arr의 원소들 중 최댓값을 최소공배수의 candidate로 설정
3. arr의 모든 원소로 나누어떨어지는 수가 나올때까지 candidate 1씩 증가
4. 모든 원소로 나누어떨어지는 경우 리턴.

 

<코드(Python)>

def solution(arr):
    arr.sort()
    for i in range(len(arr)):
        for j in range(i):
            if arr[j] != 0 and arr[i] % arr[j] == 0:
                arr[j] = 0
            
    candidate = max(arr)
    while True:
        for a in arr:
            if a != 0 and candidate % a != 0:
                break
            if a == arr[-1]:
                return candidate
        candidate += 1
    

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest