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

✨ 피자 나눠 먹기 (2)

나의 풀이

✅ 문제 요약

n명이 남김 없이 같은 조각의 피자를 먹는 최소의 판 수 구하기

function solution (n) {
    for(let i = 1; i <= 100; i++){
        if((6 * i) % n === 0){
            return i
        }
    }
}

i는 피자의 판 수 (각 판은 6조각 → 총 6 i 조각)
`(6 i) % n === 0`인 순간이 각자 공평하게 나눠먹을 수 있는 최소 판 수

✅ 시간복잡도

최대 100까지 순회 => 최악의 경우 O(100) = O(1) : 상수시간
루프는 고정 범위 내에 돌아가므로 효율적

👉 총 시간복잡도: O(1) : 상수 시간

✅ 공간복잡도

변수 i 하나만 사용 → O(1)

👉 총 공간복잡도: O(1)

✅ 개선 포인트 (메모리 최적화)

• 실제론 100까지 돌릴 필요 없이, LCM(6, n) / 6 으로 바로 구할 수 있음
• 최소공배수(Lowest Common Multiple) 개념 사용하면 더 간결하게 가능

function solution(n) {
  function 최대공약수(a, b) {
    if (b === 0) {
      return a;
    } else {
      return 최대공약수(b, a % b); // 나머지
    }
  }

  function 최소공배수(a, b) {
    return (a * b) / 최대공약수(a, b);
  }

  return 최소공배수(6, n) / 6;
}

function solution(n) {
  const 최대공약수 = (a, b) => b ? 최대공약수(b, a % b) : a;
  const 최소공배수 = (a, b) => (a* b) /최대공약수(a, b);
  return 최소공배수(6, n) / 6;
}

📌 해석 : 6조각짜리 피자를 n명이 공평하게 나눌 수 있는 최소 공배수를 구한뒤
그걸 6으로 나눈 값이 최소 판 수

✅ 결론

항목	기본 반복문 풀이	수학 최적화 풀이
시간복잡도	O(1) (최대 100번 루프)	O(log n) (gcd 사용)
공간복잡도	O(1)	O(1)
가독성	간단	수학 지식이 있으면 더 간단
확장성	낮음	높음 (6조각 외 다른 문제 확장 쉬움)