[프로그래머스/Kotlin] N개의 최소공배수 (Lv. 2)

Algorithm/kotlin

[프로그래머스/Kotlin] N개의 최소공배수 (Lv. 2)

나연쓰 2024. 3. 29. 16:35

문제

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

제한 사항

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

입출력 예

풀이 방법

1. 내 코드

내가 생각한 방법은 주어진 배열에서 가장 큰 값을 찾고, 반복문을 돌며 나머지 배열의 값들이 가장 큰 값에 나누어 떨어져지는지 확인하는 방법이다.

현재 배열에서 가질 수 있는 가장 작은 최소공배수는 배열에서 가장 큰 값이기 때문에 max값이 초점을 잡았다.

그리고 만약 나누어 떨어지지 않는 값이 있다면 현재의 max값은 최소공배수가 될 수 없으므로 max값에 (n+1)을 해줘야한다.

1. 배열을 오름차순 정렬하고, 배열의 마지막 인덱스 값을 max라는 변수에 초기화한다.

var arrSorted = arr.sorted()
var max = arrSorted[arrSorted.size-1]

2. 배열을 돌면서 0으로 나누어 떨어지는지 확인하기 위해 cnt 변수를 만들어줬다.

while문에서 빠져나갈 수 있는 조건은 배열의 길이 - 1 (1을 뺀 이유는 max 값은 빠졌기 때문) 와 cnt 값이 같을 때이다.

반복문을 돌며 나누어 떨어지는지 확인하고 나누어 떨어진다면 cnt의 값을 증가시키고 떨어지지 않는다면 멈춤으로써

조금이라도 시간을 줄여본다.

그리고 꼭 num을 1 증가시켜줘야한다. 현재 예제에서는 max 값이 14이고 그 다음 유력한 최소공배수는 14 * 2 이기 때 문 !

var cnt = 0
var num = 1
while(cnt != arrSorted.size-1){
    cnt = 0
    for(i in 0 until arrSorted.size-1){
        if((num * max) % arrSorted[i] == 0){
            cnt++
        }else{
            break
        }
    }
    num++
}

3. 마지막으로 while문을 탈출했을 때 만나는 코드다. max에 num-1을 곱해준다. 1을 빼는 이유는 위의 코드에서 마지막에 num++를 해줬기 때문이다.

answer = (num-1) * max

2. 유클리드 호제법(다른 사람 풀이)

두 개의 값을 계속 비교하면서 최소 공배수를 찾는다. 이 때 두 수 a,b의 최소 공배수는 a * b / (a,b의 최대공약수) 이다.

1. 배열의 첫번째 값을 answer에 담는다.

var answer = arr[0]

2. arr를 반복하며 최종적으로 answer에 담기는 값이 배열의 최소 공배수이다.

arr.forEach{
    answer = lcm(answer, it)
}

3. a, b의 최소 공배수는 a * b / (a,b의 최대 공약수) 이다.

fun lcm(a: Int, b: Int) = a * b / gcd(a, b)

4. 최대 공약수는 a,b 중 큰 값을 작은 값으로 나눈 나머지, 작은 값을 계속 구하며 작은 값이 0이 될 때까지 반복하면 된다.

이 때 작은 값이 0이 될 때 나머지 하나 값이 최대공약수가 된다.

fun gcd(a: Int, b: Int) : Int {
    return if(a < b) {
        if(a == 0) b else gcd(a, b%a)
    }else{
        if(b == 0) a else gcd(b, a%b)
    }
}

코드

1. 내 코드(시간 잡아먹는 괴물..)

class Solution {
    fun solution(arr: IntArray): Int {
        var answer = 0
        var arrSorted = arr.sorted()
        var max = arrSorted[arrSorted.size-1]
        println(max)
        
        var cnt = 0
        var num = 1
        while(cnt != arrSorted.size-1){
            cnt = 0
            for(i in 0 until arrSorted.size-1){
                if((num * max) % arrSorted[i] == 0){
                    cnt++
                }
            }
            // println(cnt)
            num++
        }
        answer = (num-1) * max
        return answer
    }
}

2. 유클리드 호제법 사용

class Solution {
    fun solution(arr: IntArray): Int {
        var answer = arr[0]
        
        arr.forEach{
            answer = lcm(answer, it)
        }
       
        return answer
    }
    
    fun lcm(a: Int, b: Int) = a * b / gcd(a, b)
    
    fun gcd(a: Int, b: Int) : Int {
        return if(a < b) {
            if(a == 0) b else gcd(a, b%a)
        }else{
            if(b == 0) a else gcd(b, a%b)
        }
    }
}

느낀점

기존 내 풀이랑 유클리드 호제법으로 풀었을 때의 시간 차이가 어마무시하다 ...

앞으로 꼭 기억해야지 ..