-
[Swift] 알고리즘 공부 - 최대공약수와 최소공배수알고리즘 공부/프로그래머스 2023. 4. 17. 01:40
문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
- 두 수는 1이상 1000000이하의 자연수입니다.
입출력 예
n m return 3 12 [3, 12] 2 5 [1, 10] 설명
1. 최대공약수는 1부터 n이나 m중 하나를 골라 한번씩 n과 m의 모두 나누어 떨어지는지 확인
2. 나누어 떨어지는 수중 가장 큰값이 최대공약수
3. 최소공배수는 n과 m을 최대공약수로 모두 나눈수를 곱한뒤 최대공약수를 곱해주면 최소공배수
func solution(_ n:Int, _ m:Int) -> [Int] { var min = 0 var max = 0 max = (1...n).filter { n % $0 == 0 && m % $0 == 0 }.max()! min = (n / max) * (m / max) * max return [max, min] }
찾아보니 최대공약수 최소공배수를 간단히 푸는 방법은 유클리드 호제법을 사용하면 간단하게 풀수 있다고 한다.
밑에는 다른사람의 풀이다.
/// 최대공약수 func gcd(_ a: Int, _ b: Int) -> Int { if b == 0 { return a } else { return gcd(b, a % b) } } /// 최소공배수 func lcm(_ a: Int, _ b: Int) -> Int { return a * b / gcd(a, b) } func solution(_ n:Int, _ m:Int) -> [Int] { return [gcd(n, m), lcm(n, m)] }
'알고리즘 공부 > 프로그래머스' 카테고리의 다른 글
[Swift] 알고리즘 공부 - 이상한 문자 만들기 (0) 2023.04.18 [Swift] 알고리즘 공부 - 3진법 뒤집기 (0) 2023.04.17 [Swift] 알고리즘 연습 - 직사각형 별찍기 (0) 2023.04.16 [Swift] 알고리즘 공부 - 행렬의 덧셈 (0) 2023.04.16 [Swift] 알고리즘 공부 - 타겟 넘 (0) 2023.03.30