팩토리얼

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

프로그래머스

---

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

• i! ≤ n

---

제한사항

• 0 < n ≤ 3,628,800

---

입출력 예

n	result
3,628,800	10
7	3

---

입출력 예 설명
입출력 예 #1

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

입출력 예 #2

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

---

i의 팩토리얼이 n 이하인 가장 큰 i를 찾는 문제입니다.

팩토리얼 함수는 재귀함수로 구현할 수 있는 재귀함수인데요, 이번에 재귀로 팩토리얼을 구현해보겠습니다.

파이썬으로 풀어보겠습니다.

# 팩토리얼 재귀 함수
def factorial(i):
    # 초기값 1일 때 1
    if i == 1:
        return 1
    # 나머지 값들은 i를 계속 곱한 값입니다.
    else:
        return factorial(i - 1) * i

def solution(n):
    # 10 이하의 모든 i에 대해서 반복합니다.
    for i in range(10, -1, -1):
        # 팩토리얼 결과가 n보다 작다면
        if factorial(i) <= n:
            # 가장 큰 i이므로 반환합니다.
            return i

문제에서 n이 3,628,800 이하라고 설정해주었는데, 이건 10!의 값을 뜻합니다.

따라서 i의 범위는 자연스럽게 0 ≤ i ≤ 10이라는 것을 알 수 있죠. 따라서 반복문에서 가장 큰 10부터 계속 값을 계산해서 n 이하가 되는 최대 i 값을 찾도록 할 수 있습니다.

 

재귀함수의 가장 큰 문제는 메모리 소모가 크다는 거죠. 메모이제이션을 사용한 방법은 다음과 같습니다.

def solution(n):
    memo = {} # 팩토리얼 배열을 저장할 memo
    def factorial(i): # 팩토리얼 함수
        if i in memo: # memo안에 i가 기록되있다면
            return memo[i] # 해당 값 반환
        if i == 0 or i == 1: # i가 0이나 1이면
            return 1 # 초기값 1 설정
        return factorial(i - 1) * i # 이전 값 * i로 현재 값 반환

    for i in range(10, 0, -1): # i 범위인 1 이상 10 이하에서 비교
        if factorial(i) <= n: # i의 팩토리얼이 n보다 작을 때
            return i # i를 반환합니다.

 

팩토리얼을 구현하는 문제였습니다.