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

문제

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

풀이

유클리드 호제법

• 2개의 자연수의 최대 공약수를 구하는 알고리즘
  a와 b가 정수이고, a를 b로 나눈 나머지가 r이라고 하고 a와 b의 최대공약수를 (a,b)라고 하면 다음이 성립한다.
  (a,b) = (b,r)

1. 위에서 설명한 유클리드 호제법을 코드로 구현한다.
2. 유클리드 호제법 함수(이하 최대공약수 함수)에 입력으로 받은 배열의 첫 번째, 두 번째 원소를 넣어 결과값을 도출한다.
3. 해당 결과값을 사용하여 첫 번째, 두 번째 원소의 최소공배수를 구하는 함수를 구현한다. ($lcm = a * b / gcd(a,b)$ // 최소공배수 : LCM, 최대공약수 : GCD)
4. 입력으로 받은 배열의 모든 값에 위의 함수를 적용하여 배열 전체 원소릐 최소공배수를 구할 수 있다.

import Foundation

func solution(_ arr:[Int]) -> Int {
    func gcd(_ a: Int, _ b: Int) -> Int {
        let i = a % b
        if i != 0 { return gcd(b, i) } // 나머지가 존재할 때
        else { return b } // 나머지가 없다면(a와 b가 같은 경우나 a가 b의 정수배일 때) b를 반환
    }
    
    func lcm(_ a: Int, _ b: Int) -> Int {
        return a * b / gcd(a, b)
    }
    
    return arr.reduce(1){lcm($0, $1)}
}

회고

• 이런 문제를 해결할 때는 유클리드 호제법을 알고있느냐 등의 배경지식이 많은 도움이 될 것 같다.
• 이번에 사용해봤으니, 구현하는 방법과 사용하는 방법들을 까먹지 않고 가끔 리마인드 하면 코딩테스트 대비하는 입장에서 잃을 것이 없을 것 같다!