[Swift Algorithm] 최대공약수와 최소공배수 Programmers(Lv.1)

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

제한 조건

• 두 수는 1이상 1000000이하의 자연수입니다.

 

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

 

내 문제 풀이

func solution1(_ n:Int, _ m:Int) -> [Int] {
    var max = 0 // 최대공약수
    var a = 0 // 입력받은 수 중에 더 큰 수
    
    // 더 큰 수를 변수 a에 넣음
    if n > m {
        a = n
    }
    else {
        a = m
    }
    
    // 최대공약수 구하는 반복문
    // 더 큰 수 a가 0이 될 때까지 1씩 -하며 n, m을 a로 나눠보다가 두 수 모두 나눠떨어질 때 종료
    while a > 0 {
        if (n%a == 0 && m%a == 0) {
            max = a
            break
        }
        else {
            a -= 1
        }
    }
    
    // 반복문을 통해 구한 최대공약수, 그리고 최대공약수를 이용한 최소공배수 구하는 공식을 사용하여 배열 리턴
    return [max, n*m/max]
}

• 입력받은 두 수중에 큰 수를 판별하고, 최대공약수를 구한 다음 최소공배수는 최대공약수를 이용한 공식으로 해결했다.
• 최대공약수는 큰 수 a부터 입력 받은 두 수를 나눠보다가 두 수 모두 나눠떨어질 때를 구했다.

 

💡 피드백

• 생각해보니 굳이 큰 수로 나누지 않고 작은 수부터 나눠도 가능한데,, 그렇게 하면 효율이 훨씬 좋아진다.

 

---

 

🖍 [ 추가 ] 1주일 후 다시 풀어보기

func solution(_ n:Int, _ m:Int) -> [Int] {
    var min = 0
    var max = 0
    
    if n > m { max = n; min = m }
    else { max = m; min = n }
    
    var gcd = min
    
    while gcd != 1 {
        if max % gcd == 0 && min % gcd == 0 {
            break
        }
        
        gcd -= 1
    }
    
    return [gcd, m*n/gcd]
}

• 두 수중 더 작은 수로 두 수를 나눠주며 모두가 나눠떨어질 때 최대공약수를 구했다.
• 첫 번째로 풀었던 코드보다 훨씬 간결하게 잘 푼 듯 하다.

 

---

 

➕🖍 [ 또! 추가 ] 1주일 후 또 다시 풀어보기

func solution(_ n:Int, _ m:Int) -> [Int] {
    var gcd = 0
    var min = 0
    n > m ? (min = m) : (min = n)
    for i in (1...min).reversed() { if n%i==0 && m%i==0 { gcd = i; break } }
    return [gcd, (n*m)/gcd]
}

• 로직은 거의 비슷하지만 if, else 대신 삼항연산자를 사용했고, while 대신 reversed 메소드를 이용해서 for문으로 반복문을 돌렸다.
• 가독성도 훨씬 좋고 매우 간결해졌다.

 

---

 

문제

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