문제 개요
어떤 수 a가 주어졌을 때, n! = a를 만족하는 정수 n을 찾는 것이 이번 글의 목표입니다. 팩토리얼은 n! = n × (n−1) × (n−2) × … × 1로 정의되며, 조건을 만족하는 정수 n이 존재하지 않으면 −1을 반환해야 합니다.
예를 들어 입력이 a = 120이라면, 5! = 5 × 4 × 3 × 2 × 1 = 120이므로 출력은 5가 됩니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- i := 0, num := 1로 초기화합니다.
- 빈 리스트 L을 생성합니다.
- i < a인 동안 반복합니다.
- i에 num의 팩토리얼 값을 저장합니다.
- i를 리스트 L의 끝에 추가합니다.
- num을 1 증가시킵니다.
- a가 리스트 L에 있으면 (L에서 a의 인덱스) + 1을 반환합니다.
- 그렇지 않으면 −1을 반환합니다.
구현 예제
import math
class Solution:
def solve(self, a):
i, num = 0, 1
L = []
while i < a:
i = math.factorial(num)
L.append(i)
num += 1
if a in L:
return L.index(a) + 1
else:
return -1
ob = Solution()
print(ob.solve(120))입력
120
출력
5
동작 원리 살펴보기
입력이 120일 때 코드의 실행 과정은 다음과 같습니다.
- num = 1 → 1! = 1, L = [1]
- num = 2 → 2! = 2, L = [1, 2]
- num = 3 → 3! = 6, L = [1, 2, 6]
- num = 4 → 4! = 24, L = [1, 2, 6, 24]
- num = 5 → 5! = 120, L = [1, 2, 6, 24, 120] → 반복 종료
반복이 끝난 뒤 120은 리스트의 인덱스 4에 위치하므로, 인덱스에 1을 더한 5가 최종 결과로 반환됩니다.
더 효율적인 개선 방법
위 방법은 모든 팩토리얼 값을 리스트에 저장하므로 추가적인 메모리를 사용합니다. 팩토리얼은 이전 값에 새 숫자를 곱하기만 하면 되기 때문에, 리스트 없이 누적 곱만으로도 동일한 결과를 얻을 수 있습니다.
class Solution:
def solve(self, a):
num, fact = 1, 1
while fact < a:
num += 1
fact *= num
return num if fact == a else -1
ob = Solution()
print(ob.solve(120)) # 출력: 5이 방식은 불필요한 저장 공간 없이 O(1) 수준의 공간 복잡도로 동작하므로, 입력값이 커져도 훨씬 효율적으로 처리할 수 있습니다.
마치며
역 팩토리얼 문제는 팩토리얼의 성질을 활용해 주어진 수를 거슬러 올라가며 추적하는 대표적인 연습 문제입니다. 리스트 기반 구현은 직관적이지만, 누적 곱 방식으로 개선하면 메모리와 실행 시간 측면에서 모두 유리해집니다. 상황에 맞는 구현 방식을 선택해 보시기 바랍니다.