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

thumbnail

안녕하세요. 이번에는 프로그래머스 N개의 최소 공배수 문제를 풀어보려고 합니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

---

Problem

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

 

[제한 사항]

○ arr은 길이 1 이상, 15 이하인 배열입니다.

○ arr의 원소는 100 이하인 자연수입니다.

사진 1. 입출력 예

---

Solution

import kotlin.math.*

class Solution {
    fun solution(arr: IntArray): Int {
        var answer = arr[0]
      
        (1 until arr.size).map {
            answer = answer * arr[it] / getGcd(max(answer, arr[it]), min(answer, arr[it]))    
        }
        
        return answer
    }
    
    tailrec fun getGcd(a: Int, b: Int): Int {
        return if(b == 0) a else getGcd(b, a % b)
    }
}

이번에는 최소 공배수를 구하는 getGcd를 꼬리재귀 함수로 구현해 주었습니다. 여기서 꼬리재귀가 궁금하시다면, 아래의 링크로 들어가면 됩니다.

[Kotlin] tailrec 꼬리 재귀 함수에 대하여 알아보기

answer을 두 수의 최소 공배수로 만들면서 문제를 해결할 수 있었습니다.

 

1. 다른 사람 코드

class Solution {
    fun solution(arr: IntArray): Int {
        var answer = 1
        while(true) {
            var x = 0
            for(a in arr) x += answer%a
            if(x==0) return answer
            answer++
        }
        return answer
    }
}

저의 코드와 다르게 반복문으로 푼 문제가 있어서 가져와봤습니다.

코드 분석

1. x를 0으로 초기화해줍니다.

2. answer의 값이 배열의 값으로 나누어 떨어지는지 확인합니다.

3 - 1. 여기서 만약 모든 값이 떨어지면 최소 공배수의 값이므로 return 해줍니다.

3 - 2. 만약 값이 떨어지지 않는다면 answer을 증가시키고 다시 1 ~ 3번의 작업을 반복해 줍니다.

 

이렇게 while문을 통해서 구현하는 방법이 있다. 하지만 최소 공배수의 값이 커질수록 반복되는 횟수가 많아지기 때문에 속도 면에서 재귀 함수보다 좀 더 시간 복잡도면에서는 효율적이라고 생각됩니다. 다른 의견이나 다른 방법이 있으시면 언제든지 편하게 댓글로 가르쳐주시면 감사하겠습니다! 

---

Performance

1. 내가 작성한 코드	2. 다른 사람 코드