문제 설명

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

접근 방법

처음에는 모든 수들을 공통으로 나눌 수 있는 수를 찾아 나눌 수 있을 때까지 나누고 나누는 수들을 따로 저장한 뒤, 마지막에 나눌 수 없어지면 나눈 수들과 마지막에 도출된 수들을 모두 곱하는 방식으로 코드를 작성하였다. 테스트 케이스는 통과했지만 정확도 테스트에서 통과하지 못했다.

질문하기를 통해 접근 방법을 알아보고 뒤에서부터 두 수를 빼내어 이들의 최소공배수를 구한 뒤에 그 최소 공배수를 배열에 다시 넣는 과정을 배열의 길이가 1이 될때까지 반복하면 배열에 남은 수가 결국은 N개의 최소공배수가 된다는 사실을 알았다.

이 방법을 토대로 하여 최소공배수를 구하는 함수를 따로 작성하여 이 함수를 여러번 반복하도록 하여 arr의 길이를 줄여나가 최종 수를 구할 수 있었다.

• 최소공배수를 구하는 함수 lcm을 a, b를 인자로 갖도록하여 선언한다.
  -> 현재 나누는 수를 나타내는 변수 cur을 1로 선언한다.
  -> 최소공배수를 담을 변수 result를 1로 선언한다.
  -> cur이 a와 b 중 더 작은 수보다 더 작을동안 반복하는 while문을 돌린다.
  --> cur을 1 증가시킨다. (cur은 2부터 시작해야 한다.)
  --> 만약 a, b가 모두 cur에 나누어 떨어지는 경우,
  ---> result에 cur을 곱한다.
  ---> a, b를 cur로 나눈 값으로 갱신한다.
  ---> cur을 1로 갱신한다.
  -> result에 a*b를 곱한다.
  -> result를 반환한다.
• arr의 길이가 2 이상일 동안 반복하는 while문을 돌린다.
  -> 임시 변수 num1에 arr.pop()의 반환값을 넣는다.
  -> 임시 변수 num2에 arr.pop()의 반환값을 넣는다.
  -> arr에 lcm(num1, num2)의 반환값을 넣는다.
• arr[0]을 반환한다.

solution.py

def solution(arr):
    def lcm(a, b):
        cur=1
        result=1
        while cur<min(a, b):
            cur+=1
            if a%cur==0 and b%cur==0:
                result*=cur
                a//=cur
                b//=cur
                cur=1
        result*=(a*b)
        return result
    while len(arr)>=2:
        num1=arr.pop()
        num2=arr.pop()
        arr.append(lcm(num1, num2))
    return arr[0]