프로그래머스/Lv0/팩토리얼

문제 설명

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

---

처음 작성한 풀이

function solution(n) {
    if(n===1) return 1
    function fac(num){
        let result = 1;
        if(num === 1 || num === 0){
            return result;
        }else{
            for(i=1;i<=num;i++){
                result *= i;
            }
            return result;
        } 
    }
    let answer = 0;
    while(fac(answer)<n ){
        answer+=1;
        if(fac(answer)>n){ return answer-1;}
    }
    return answer;
}

주어진 숫자 num을 기준으로 num!을 return하는 fac 함수를 선언하고 주어진 조건에 맞는 num을 찾을때까지 while 반복문을 적용했다.

시간 복잡도는 O(sqrt(n)) 으로 적당하지만 최적화가 되어있지 않은 코드이다.

그래서 다른 분들의 풀이와 Gpt와의 대화를 통해 최적화했다.

---

function solution(n) {
    for(let i = 1, v = 1; true; v *= ++i) if(v > n) return --i;
}

function solution(n) {
  let factorial = 1;
  let i = 1;
  while (factorial * (i + 1) <= n) {
    factorial *= ++i;
  }
  return i;
}

각각 for문 while문 안에서 연산을 다 처리하는 방식이다. 두 코드 다 시간 복잡도는 O(sqrt(n))로 동일하고 코드가 더욱 간결해졌다.

여기서 for 문안의 true는 return 하기 전까지 무한반복(무한루프)를 돌리라는 의미이다. 실질적으로는 while문과 동일한 방식이다.

문제를 다시 풀어보니 쉽게 풀 수 있었는데 처음에는 너무 복잡하게 접근 했던 것 같다.