Algorithm / N개의 최소공배수

문제

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

1) 문제 풀이

func solution(_ arr:[Int]) -> Int {
    var top = arr.max() ?? 0
    var currentLCM = top
    var lcm = [Bool](repeating: false, count: arr.count)
    
    while lcm.contains(false) {
        arr.enumerated().forEach { i, num in
            if currentLCM % num == 0 {
                lcm[i] = true
            }
        }
        
        if !lcm.contains(false) {
            break
        } else {
            lcm = lcm.map { _ in false } // 초기화
            currentLCM += top
        }
    }
    
    return currentLCM
}

결과

2) 코드 개선

❌ 문제점 분석

• 비효율적인 완전탐색 방식
  • currentLCM에서 시작하여 모든 수로 나누어 떨어지는 수가 나올 때까지 계속 += top을 반복하는 방식
  • 이는 숫자가 클수록 계산량이 기하급수적으로 증가하게 됨
  • [100, 200, 300, 400, 500, 600]과 같은 입력이 들어올 경우 거의 무한 푸르에 가까운 반복이 발생됨
• lcm 배열 초기화 방식의 불안정성
  • lcm = lcm.map { _ in false }는 매 반복마다 초기화되긴 하지만, 로직이 지저분하고 가독성이 떨어짐
  • Set을 써서 체크하거나, 매번 직접 조건을 검사하는 방식으로 대체 가능
• 수학적 원리가 전혀 활용되지 않음
  • LCM 계산은 수학적 원리를 활용하는 것이 더욱 빠르게 계산할 수 있음
  • LCM(a,b)=a*b/GCD(a,b) => LCM(a,b,c)=LCM(LCM(a,b),c)

✅ 개선 포인트

• reduce()로 배열을 돌며 두 수씩 LCM을 누적 계산
• 두 수의 GCD는 유클리드 알고리즘으로 계산
• LCM 계산은 수학적 공식을 활용

func solution(_ arr:[Int]) -> Int {
    func gcd(_ a: Int, _ b: Int) -> Int {
        var a = a
        var b = b
        while b != 0 {
            let temp = a % b
            a = b
            b = temp
        }
        return a
    }
    
    func lcm(_ a: Int, _ b: Int) -> Int {
        return a * b / gcd(a, b)
    }
    
    return arr.reduce(1) { lcm($0, $1) }
}

결과