프로그래머스 Lv. 2 Swift 알고리즘 - N개의 최소공배수

N개의 모든 원소를 공통으로 하는 최소공배수를 찾는 문제이다.

 

최소공배수와 최대공약수는 항상 연관관계가 있다.

두 수를 기준으로 두 수의 곱셈을 최대공약수로 나누었을때 최소공배수가 나온다.

 

문제 자체는 이해하기 쉬운데 코드 짜는 것이 생각보다 복잡했다. 특히 배열을 직면했을때 모든 원소를 전부 생각하는 버릇이 있어서 머릿속에서 다루는 사이즈가 자꾸 커져 코드가 복잡해지는 것 같다. 그래서 다른 사람들이 푼 코드를 찾아보다보니 두 개의 원소끼리 비교하여 최대공약수를 찾아내고 그 다음 원소와 이를 비교하여 또 최대 공약수를 찾아내고.. 하는 방식을 보았다. 굉장히 단순하지만 앞 원소들의 최소공배수와 뒤 원소를 비교하고 지워나간다는 개념은 머릿속에 없었다... 역시 알고리즘은 수학문제처럼 다양한 방식으로 풀고, 다양한 해답을 찾아보고, 안풀리면 답안도 보고 해야하는 것 같다.

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. 최소공배수를 구하기 위해 필요한 최대공약수를 구하는 함수를 만든다.
2. 인수분해가 더이상 되지 않을 때까지 나눠 최대공약수를 찾는다.
3. 최소공배수를 구할 수 있는 함수를 만든다.
4. 정수 c와 d를 곱해주고 그 둘의 최대공약수를 나눠주면 최소공배수가 된다.
5. arr배열에 있는 원소들을 하나씩 누적으로 비교하여 최소공배수를 찾아간다.
6. 이때 reduce의 initialResult는 1로 시작해야 값에 오류가 생기지 않는다.

 

 

* 코드

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

func leastCommonMultiple(_ c: Int, _ d: Int) -> Int {
    return (c * d) / greatestCommonDivisor(c, d)
}

func solution(_ arr:[Int]) -> Int {
    return arr.reduce(1) { leastCommonMultiple($0, $1) }
}

 

 

정리(Today I Learned)

1. 클로저는 정말 편리하지만... 아직도 완전히 이해를 못했다...!
2. 클로저 공부를 많이하고 Apple에서 제공하는 Document를 더 적극적으로 이용해야 될 것 같다.
3. 고차함수는 당장 쓸때는 이해하며 쓰는데 시간이 지나고 다시 사용하려면 모르겠다... 이건 완전히 이해한게 아니겠지...