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

문제

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

자연수 array 입력받으면 array 수들의 최소 공배수 return

접근 방법

유클리드 알고리즘을 사용하면 두 수의 최소공배수를 빠르게 구할 수 있다.

> 유클리드 알고리즘

두 수 a, b가 있으면

최소 공배수는 a*b / 최대 공약수 인데,

최대 공약수 구하는 방법은

r = a&b 에서 나눈 나머지를 r이라고 하면

if r == 0 {b는 최대 공약수}

else {

​ b = a

​ a = r

​ // 로 해서 다시 반복

}

하다 보면 최대 공약수가 구해진다.

위 과정은 소인수 분해를 하는 과정을 사용한 것이다. 최대 공약수를 구했으면 이 값을 이용해 최소 공배수를 구할 수 있다.

최소공배수 = a*b/최대공약수

하지만 위 문제는 두 수를 비교하는 문제가 아니라 여러 수를 비교하는 문제이기 때문에 까다롭다.

해결

이는 stack을 이용하면 풀 수 있다.

arr안의 갯수가 2 이상일 경우, 두 수를 pop 해서 최소공배수를 구해준 뒤 push 해주는 식으로 반복해주면 된다.

코드

	func solution(_ arr:[Int]) -> Int {
	var arr = arr
	while arr.count >= 2 {
	let v1 = arr.popLast()!
	let v2 = arr.popLast()!
	arr.append(gcm(v1, v2))
	}
	return arr.first!
	}
	func gcd(_ b: Int, _ s: Int) -> Int {
	let r = b%s
	return r == 0 ? s : gcd(s, r)
	}
	func gcm(_ b: Int, _ s: Int) -> Int {
	return b*s / gcd(b, s)
	}

view raw N개의최소공배수.swift hosted with ❤ by GitHub