[Programmers] #120848 - 팩토리얼 [Java][C++][Python]

문제 링크

---

1. 아이디어

n의 상한이 $3{,}628{,}800 = 10!$이므로 답이 될 수 있는 i는 1부터 10까지뿐이다. $1!$부터 $10!$까지 미리 구해 두고 큰 쪽부터 내려오며 n 이하가 되는 첫 i를 반환하면 된다. n은 항상 1 이상이고 $1! = 1$이므로 조건을 만족하는 i는 반드시 존재한다.

---

2. 복잡도

접근	시간	공간
풀이	$O(1)$	$O(1)$

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int n) {
        int[] fact = new int[1 + 10];
        fact[0] = 1;

        for (int i = 1; i <= 10; i++) {
            fact[i] = fact[i - 1] * i;
        }

        for (int i = 10; i >= 1; i--) {
            if (fact[i] <= n) return i;
        }

        return -1;
    }
}

#include <bits/stdc++.h>
using namespace std;

int fact[1 + 10] = {1};

int solution(int n) {
    for (int i = 1; i <= 10; i++) {
        fact[i] = fact[i - 1] * i;
    }

    for (int i = 10; i >= 1; i--) {
        if (fact[i] <= n) return i;
    }

    return -1;
}

import math


def solution(n):
    return max(i for i in range(1, 11) if math.factorial(i) <= n)

math.factorial(i)로 각 i의 팩토리얼을 바로 구할 수 있다.

---