[programmers] 피자 나눠 먹기 (2) 파이썬 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/120815

프로그래머스

문제

 

문제 자체는 쉬운 문제였다. 최소 공배수를 구해야겠구나 라고 생각하고, for 문으로 피자 판 수를 1부터 시작해서 필요한 피자 판 수를 찾을 때까지 증가시키면서 모든 사람이 동일한 수의 조각을 가질 수 있는지 확인되면 그 때의 피자 판 수를 return 시키는 식으로 풀었다.

 

1.  for문 풀이 👉 정답

def solution(n):
    for i in range(1, 6 * n + 1):
        if (6 * i) % n == 0:
            return i

 

n 자체의 크기도 크지 않고 (1 <= n <= 100) for문도 하나밖에 없기 때문에 시간복잡도 또한 아주 양호하다.

 

2.  math.gcb 모듈 풀이 👉 정답

문제를 다 푼 후 다른 적합한 풀이가 더 있나 찾아보다, 최대 공약수와 최소 공배수를 위한 모듈이 있는 것을 발견했다.

 

[관련 포스팅 👇]

[Python] 파이썬에서 최소 공배수 함수로 구하기

 

알아낸 모듈로 문제 풀어봐야 직성이 풀리는 나 ..

import math

def solution(n):
    lcm = n * 6 // math.gcd(n, 6)
    return lcm // 6

 

먼저 6과 n의 최소 공배수를 구한 다음, 구한 최소 공배수를 6으로 나눠서 필요한 피자 판 수를 구했다.

---

3.  시간 복잡도 비교

for문 풀이법에서는 최악의 경우, n * 6 번 반복해야 하기 때문에 시간 복잡도는 O(n)이 될 것이다. (각 반복에서 (i * 6) % n == 0 조건을 확인하는 연산은 O(1))

 

math.gcd 함수같은 경우 유클리드 알고리즘을 사용하여 두 수의 최대 공약수를 구한다고 한다. 유클리드 알고리즘의 시간 복잡도는 O(log(min(a,b))) 이다.

• 최소 공배수를 구하고 이를 6으로 나누는 연산은 O(1)이다.

따라서, math.gcd를 사용하는 방법의 전체 시간 복잡도는 O(log(min(n,6))) = O(log(n)) 가 될 것이다.

---

마치며

즉! 정리해보면 시간 복잡도 측면에서 math.gcd를 사용하는 방법이 더 효율적이라고 할 수 있겠다. (특히 n이 큰 값일 때 더욱) 또한 Python 내장 함수를 활용하기 때문에 코드도 간결해질 것.

 

쉬운 문제였지만 새로운 모듈을 알아가서 기분이 좋다. 성능이 중요한 문제에서는 for문 대신 이 모듈을 써버릇 해야겠음!