[Algorithm] Nκ°μ μ΅μ곡배μ (μ ν΄λ¦¬λ νΈμ λ²)
π₯ λ¬Έμ
λ μμ μ΅μ곡배μ(Least Common Multiple)λ μ λ ₯λ λ μμ λ°°μ μ€ κ³΅ν΅μ΄ λλ κ°μ₯ μμ μ«μλ₯Ό μλ―Έν©λλ€. μλ₯Ό λ€μ΄ 2μ 7μ μ΅μ곡배μλ 14κ° λ©λλ€. μ μλ₯Ό νμ₯ν΄μ, nκ°μ μμ μ΅μ곡배μλ n κ°μ μλ€μ λ°°μ μ€ κ³΅ν΅μ΄ λλ κ°μ₯ μμ μ«μκ° λ©λλ€. nκ°μ μ«μλ₯Ό λ΄μ λ°°μ΄ arrμ΄ μ λ ₯λμμ λ μ΄ μλ€μ μ΅μ곡배μλ₯Ό λ°ννλ ν¨μ, solutionμ μμ±ν΄ μ£ΌμΈμ.
π€ νμ΄ λ°©λ²
- arr[0]κ³Ό arr[1]μ μ΅λ곡μ½μλ₯Ό μ ν΄λ¦¬λ νΈμ λ²μ μ΄μ©νμ¬ κ΅¬νλ€.
- 1λ²μμ ꡬν μ΅λ곡μ½μλ₯Ό μ΄μ©νμ¬ μ΅μ곡배μλ₯Ό ꡬνλ€.
- 2λ²μμ ꡬν μ΅μ곡배μλ₯Ό μ΄μ©νμ¬ arr[2]μμ μ΅λ곡μ½μλ₯Ό μ ν΄λ¦¬λ νΈμ λ²μ μ΄μ©νμ¬ κ΅¬νλ€.
- 3λ²μμ ꡬν μ΅λ곡μ½μλ₯Ό μ΄μ©νμ¬ μ΅μ곡배μλ₯Ό ꡬνλ€.
- 3, 4λ²μ λ°λ³΅νλ€.
π©π»βπ» Swift Code
import Foundation
func solution(_ arr:[Int]) -> Int {
var gcd = 0
var lcm = 0
for i in 0..<arr.count-1 {
var num1 = 0
var num2 = 0
// gcd
if i == 0 {
num1 = max(arr[i], arr[i + 1])
num2 = min(arr[i], arr[i + 1])
} else {
num1 = max(lcm, arr[i + 1])
num2 = min(lcm, arr[i + 1])
}
var r = 0
while num1 % num2 != 0 {
r = num1 % num2
num1 = num2
num2 = r
}
gcd = num2
// lcm
if i == 0 {
lcm = arr[i] * arr[i + 1] / gcd
} else {
lcm = lcm * arr[i + 1] / gcd
}
}
return lcm
}
μ½λ©ν μ€νΈ μ°μ΅ - Nκ°μ μ΅μ곡배μ
λ μμ μ΅μ곡배μ(Least Common Multiple)λ μ λ ₯λ λ μμ λ°°μ μ€ κ³΅ν΅μ΄ λλ κ°μ₯ μμ μ«μλ₯Ό μλ―Έν©λλ€. μλ₯Ό λ€μ΄ 2μ 7μ μ΅μ곡배μλ 14κ° λ©λλ€. μ μλ₯Ό νμ₯ν΄μ, nκ°μ μμ μ΅μ곡배
programmers.co.kr