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

 

 

 

 

🍄 프로그래머스 문제

프로그래머스

✍🏻 Github 문제 풀이

-Swift-CodingTest/프로그래머스/2/12953. N개의 최소공배수 at main · BaeJihae/-Swift-CodingTest

 

 

 

문제 설명

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

 

 

문제 풀이

나의 풀이

import Foundation

func solution(_ arr:[Int]) -> Int {
    
    // 소수 배열
    let a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    
    // 최대공약수의 소인수분해 [ 소수 : 소수의 개수 ]
    var maxDic = [Int:Int]()
    
    for num in arr {
        
        var n = num

        for i in a {
            
            var k = 0
            
            if n == 1 {      // 1인 경우 반복문 빠져 나가기
                continue
            }
            
            while n % i == 0 { // i이 n의 약수일 때
                k += 1         // 앞서 나온 값의 갯수를 체크하기 위해
                n = n / i   
                
                if ( maxDic[i] ?? 0 ) < k { // 앞서 나온 소수의 개수보다 많을 경우 업데이트
                    maxDic[i] = ( maxDic[i] ?? 0 ) + 1 
                }
            }
        }
    }
    
    // 소인수분해된 최소공배수의 값 계산
    return maxDic.reduce(1){ $0 * Int(pow(Float($1.key), Float($1.value)))}
}

최대공약수의 소수를 찾아서 풀었다.

배열의 길이의 최대개수가 15이고, arr의 원소가 100이하이므로 for문이나 반복문을 돌려도 시간이 충분할 것이라고 생각했다.

100이하의 소수 배열을 놔두고, 해당 값의 소수를 찾으며 딕셔너리에 저장했다.

이 때, 전 숫자에서 이미 소수로 저장이 되었다면, 값을 업데이트 하지 말아야 했다.

이 부분에서 많이 고민하였다. 그래서 k값을 두기로 했다.

반복문을 돌때마다 1이 올라간다는 것은 해당 소수값이 반복된다는 뜻이므로 k값보다 소수의 개수가 크거나 같다면 값을 업데이트하지 않도록 로직을 구현했다.

4번에서 케이스 오류가 났는데, 그 부분은 내가 시간을 줄이기 위해 num가 a배열에 포함이 되어있다면, 해당 값은 소수 그 자체이므로 딕셔너리에 업데이트를 하고 다음 반복문으로 넘어가도록 구현을 하였는데, 이 부분에서 딕셔너리에 업데이트를 할 때도 이미 딕셔너리에 있는 값인지 확인한 후에 갯수를 고려해서 대입을 해야했다. 더 비효율적인 코드라 그 부분을 빼니 정상적으로 작동하였다.

 

 

다른 사람 풀이

func gcd(_ a: Int, _ b: Int) -> Int {
  let r = a % b
  if r != 0 {
    return gcd(b, r)
  } else {
    return b
  }
}

func lcm(_ m: Int, _ n: Int) -> Int {
  return m / gcd(m, n) * n
}
func solution(_ arr:[Int]) -> Int {
    return arr.reduce(1) { lcm($0, $1) }
}

유클리드 호제법으로 푼 문제이다. 이 풀이를 꼭 익혀두어야 겠다.