[TIL] 프로그래머스: 피자 나눠 먹기 (2)

문제 설명

머쓱이네 피자가게는 피자를 여섯 조각으로 잘라 줍니다. 피자를 나눠먹을 사람의 수 n이 매개변수로 주어질 때, n명이 주문한 피자를 남기지 않고 모두 같은 수의 피자 조각을 먹어야 한다면 최소 몇 판을 시켜야 하는지를 return 하도록 solution 함수를 완성해보세요.

제한사항

• 1 ≤ n ≤ 100

입출력 예

n	result
6	1
10	5
4	2

제출 코드

import Foundation

func solution(_ n:Int) -> Int {
    var pizza = 0
    for i in 1...100 {
        if (i * 6) % n == 0 {
            pizza = i
            break
        }
    }
    return pizza
}

빨리 풀고 싶어서 그냥 반복문을 사용해 1부터 100까지 순회하며 확인하는 방식으로 작성했기 때문에 효율이 떨어진다.....

무엇을 간과했는지

• 최소 공배수를 이용하면 반복문 없이도 간단히 해결할 수 있다는 점을 간과했다.
• (i * 6) % n == 0 조건은 사실상 최소 공배수를 찾는 과정이므로 이를 직접 계산하는 방식으로 단순화할 수 있었다.

수정 후 코드

최소 공배수를 직접 계산하는 방식으로 수정해볼 수 있었다.

import Foundation

func solution(_ n:Int) -> Int {
    func gcd(_ a: Int, _ b: Int) -> Int {
        return b == 0 ? a : gcd(b, a % b)
    }
    
    func lcm(_ a: Int, _ b: Int) -> Int {
        return a * b / gcd(a, b)
    }
    
    return lcm(6, n) / 6
}

문법 정리

1. 최대 공약수(GCD)

   • 두 수의 최대 공약수를 유클리드 호제법으로 계산:

     func gcd(_ a: Int, _ b: Int) -> Int {
         return b == 0 ? a : gcd(b, a % b)
     }

2. 최소 공배수(LCM)

   • 두 수의 최소 공배수를 최대 공약수를 이용해 계산:

     func lcm(_ a: Int, _ b: Int) -> Int {
         return a * b / gcd(a, b)
     }