[프로그래머스] '팩토리얼' - Java

<문제 제시>

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

<예시 입출력>

---

<문제 해결 과정>

Try 1) 

int answer = 0;
        
int temp = 1;
int max = 0;

// 1부터 n까지 올라가는 팩토리얼을 검사
for(int i = 1; i <= n; i++) {

    // i부터 1씩 감소하며 1까지 내려가며 팩토리얼을 구함
    for(int j = i; j >= 1; j--) {
        // temp 라는 변수에 j를 곱해서 팩토리얼 값을 저장함
        temp *= j;

        // 이 팩토리얼 값이 n보다 커지는 순간 max에 값을 저장하고 break
        // max에 저장할때는 넘은 시점에서 판단되기때문에 넘기 전 시점을 판단하기 위해서
        // i - 1을 해주었음
        if(temp >= n) {
            max = i - 1;
            break;
        }
    }
}
System.out.println(max);


return answer;

이 코드는 이중 for문을 통해 풀고자 하였으나 모든 테스트케이스를 통과하지는 못하였다.

바깥 for문에서는 1부터 n까지 증가하는 수를 다루고

안 for문에서는 i값을 하나씩 감소시키며 temp에 누적곱을 해준다. 이 값이 n보다 커지면 안되므로 break문을 걸어주었으나 오답이었다.

Try 2)

int answer = 0;
        
int sum = 1;

for(int i = sum; i <= n; i++) {
    sum *= i;
    System.out.println("sum *= i 이후 // sum = " + sum + ", i = " + i);
    if(sum > n) {
        answer = i - 1;
        System.out.println("sum이 n보다 값이 커졌습니다. answer = " + answer + ", i = " + i);
        break;
    }

}

return answer;

조금 더 코드를 정리하여 진행해보았지만 이 또한 모든 테스트케이스를 통과하지는 못하였다. 

Solution 1)

public static int fac(int n) {
    // 만약 주어진 n이 1보다 작거나 같으면 그대로 1을 반환 (예외처리)
    if(n <= 1) {
        return 1;
    }

    // 그외의 경우 n * fac(n - 1)을 반복
    /*테스트케이스
     n = 7, i = 3)
     >> i = 3에서 6이라는 값이 나오기때문에 7보다 작을때의 가장 큰 i값을 반환하므로 i=4부터는 answer에 저장이 되지 않아
     >> 최종적으로 i = 3이 반환된다.
     fac(3) = 3 * fac(2) = 6
     fac(2) = 2 * fac(1) = 2
     fac(1) = 1

     */
    else {
        return n * fac(n - 1);
    }
}

팩토리얼을 연산할 함수를 하나 더 만들어 처리한다. 

1일 경우는 팩토리얼을 처리하지 않고 1을 그대로 반환하고 그 외의 경우에서는

n * fac(n - 1); 

즉 재귀함수 형태로 n에서 1감소한 형태를 다시 매개변수로 넣어 1이 될때까지 반복한다.

 

---

<전체코드>

public class factorial {

	public static int solution(int n) {
        int answer = 0;

        // 1~10까지 증가하는 i
        for(int i = 1; i <= 10; i++) {
        	
        	// 만약 fac함수에 i를 넣은 값이 n값보다 작거나 같으면
        	if(fac(i) <= n) {
        		// 그대로 i값 반환
        		answer = i;
        	}
        }
        return answer;
    }
	
	
	public static int fac(int n) {
		// 만약 주어진 n이 1보다 작거나 같으면 그대로 1을 반환 (예외처리)
		if(n <= 1) {
			return 1;
		}

		else {
			return n * fac(n - 1);
		}
	}
	
	public static void main(String[] args) {
		//int n = 3628800;
		int n = 7;
		
		System.out.println(solution(n));
		
	}

}

---

팩토리얼의 개념은 쉬웠지만 코드로 풀어내려고하다보니 많은 시도를 거쳐 성공할 수 있었다.

재귀함수 형태로 풀어내며 가장 큰 정수를 찾을 수 있었다.

---

문제링크)
https://school.programmers.co.kr/learn/courses/30/lessons/120848

프로그래머스