팩토리얼
2024. 8. 8. 18:00ㆍ코딩테스트 입문
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를 반환합니다.
팩토리얼을 구현하는 문제였습니다.
'코딩테스트 입문' 카테고리의 다른 글
문자열 정렬하기 (1) (0) | 2024.08.10 |
---|---|
모음 제거 (0) | 2024.08.09 |
최댓값 만들기(1) (0) | 2024.08.07 |
합성수 찾기 (0) | 2024.08.06 |
주사위의 개수 (0) | 2024.08.05 |