프로그래머스-최대공약수와 최소공배수

문제

❓유클리드 호제법

• 두 정수의 최대공약수(Greatest Common Divisor, GCD)를 효율적으로 찾기 위한 알고리즘이다.
• 접근방법
  • 두 정수 a와 b(일반적으로 a > b) a % b 나눈 나머지가 r이라고 하고 r이 만약 0이라면 b가 두 수의 최대공약수 입니다.
  • 만약 r이 0이 아니라면 a,b 최대공약수는 b와 r의 최대공약수와 같습니다. 그래서 a엔 b를 할당하고 b엔 r을 할당하고 또 a % b 나머지를 구합니다. r이 0이 될때 까지 반복합니다.

❓ 최대공배수 구하기

• 최소공배수(Least Common Multiple, LCM)를 구하는 가장 효율적인 방법은 최대공약수(GCD)를 활용하는 것입니다.
• 접근방법
  • 두 수 a * b 곱하고 최대공약수로 / 나눈값이 최대공배수 입니다.

풀이

• 삼항연산자를 이용해서 파라미터의 값 n과 m 중 더 큰 수를 변수로 선언한 a에 넣고 작은수를 b에 할당합니다.
• While문을 통해 b가 0 이 되기전까지 반복합니다. 이 과정에서는 a % b 의 나머지 값을 변수 r에 할당하고 a와 b의 값을 다시 할당합니다.(유클리드 호제법을 도입합니다.) loop가 종료되면 a에는 두수의 최대공약수가 저장됩니다.
• 빈배열에 최대공약수가 저장되있는 a와 최소공배수를 구하는 식을 리턴합니다.

func solution(_ n:Int, _ m:Int) -> [Int] {
    var a: Int = Int()
    var b: Int = Int()
    var r: Int = Int()
    
    n > m ? (a = n, b = m) : (a = m, b = n)
   
    while b != 0 {
        r = a % b
        a = b
        b = r
    }
 
    return [a, (n * m) / a]
}

solution(3,12)
solution(2,5)