N개의 최소공배수

아래 문제는 프로그래머스에서 제공하는 코딩테스트 > N개의 최소공배수의 문제입니다🧑🏻‍💻

 

문제 제시

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

제한 사항

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

입출력 예

[2,6,8,14]	168
[1,2,3]	6

문제 해결

import Foundation

func solution(_ arr:[Int]) -> Int {
    let numArr = arr.sorted(by: >)
    var result = numArr[0]
    let maxNum = result
    
    while true {
        var count: Int = 0
        for i in 1..<numArr.count {
            if result % numArr[i] == 0 {
                count += 1
            }
        }
        if count == numArr.count - 1 {
            return result
        } else {
            result += maxNum
            continue
        }
    }
}

사용된 개념

 - 반복 / 조건문

 - 탐색

 - 정렬

 

문제 뒷담화

해당 문제는 내가 느끼기에 완전탐색같이 전부 다 돌아보며 조건을 체크하는것 같았다.

먼저 큰수가 공배수의 기준이 될테니 큰수가 제일 앞으로 올 수 있도록 정렬시켜준다.

그 뒤 가장 큰수를 변수에 담아 추후 배수가 누적될 수 있도록 해준다.

그리고 배수를 누적해줄 큰 수를 상수로 하나 따로 만든다.

본격적으로 while 반복문을 조건이 부합하여 탈출할때까지 계속 돈다.

먼저 최소공배수의 조건에 맞는지 체크해줄 카운터 변수 선언한다.

그리고 반복문을 도려 두번째 인덱스부터 끝까지 돌며 나머지가 0일 경우 약수이니 카운터 변수를 1 증가시키면서

전체 배열을 돈다.

그 후 조건문을 이용해 비교한 인덱스 값들이 전부 약수일경우 탈출시켜 결과값을 반환한다.

아닐경우 큰수를 더해주며 배수를 찾아 나간다.

 

 

[참고자료]

programmers.co.kr/learn/courses/30/lessons/12953