[프로그래머스]코딩테스트 입문 팩토리얼

문제 설명

i팩토리얼 (i!)은 1부터 i까지 정수의 곱을 의미합니다. 예를들어 5! = 5 * 4 * 3 * 2 * 1 = 120 입니다. 정수 n이 주어질 때 다음 조건을 만족하는 가장 큰 정수 i를 return 하도록 solution 함수를 완성해주세요.

 

i! ≤ n

 

제한사항

0 < n ≤ 3,628,800

 

입출력 예

n	result
3628800	10
7	3

 

 

입출력 예 설명

입출력 예 #1

10! = 3,628,800입니다. n이 3628800이므로 최대 팩토리얼인 10을 return 합니다.

 

입출력 예 #2

3! = 6, 4! = 24입니다. n이 7이므로, 7 이하의 최대 팩토리얼인 3을 return 합니다.

 

 

내 풀이

def fac(k):
    result = 1
    for i in range(1, k+1):
        result *= i
    
    return result

def solution(n):
    i = 1
    while fac(i) <= n:
        i += 1
    
    answer = i - 1
    
    return answer

 

파이썬 반복문을 완벽하게 내것으로 만들지 못해서 팩토리얼 구현을 할 때 for문밖에 생각이 나지 않았던 것 같다. 

 

내풀이의 문제점

1. fac(i) 호출의 반복 계산 문제

• 문제점: solution 함수에서 while 루프가 반복될 때마다 fac(i)를 계속 호출하고 있다. 이는 fac 함수가 매번 팩토리얼을 처음부터 다시 계산한다는 의미. 따라서 i가 커지면, 팩토리얼을 중복 계산하게 되어 성능이 비효율적일 수 있다.
• 해결 방법: 팩토리얼 값이 반복적으로 재계산되지 않도록, fac(i) 값을 한 번 계산한 후 while 루프 안에서 재사용하는 것이 좋습니다.

while문으로 작성하면 성능이 향상된다.

 

gpt 풀이

def solution(n):
    i = 1
    factorial = 1
    
    while factorial <= n:
        i += 1
        factorial *= i
    
    return i - 1