[프로그래머스][L2] 최댓값과 최솟값 자바 문제 풀이 및 정답

[프로그래머스][L2] 최댓값과 최솟값 자바 문제 풀이 및 정답

 

피보나치에 대한 문제를 보면 재귀함수를 떠올릴 수 있지만 해당 문제는 재귀를 통해 풀면 안된다는게 유추되는 문제입니다. n번째 수를 1234567로 나눈 수를 구해야 하고 n은 최대 100,000까지로 주어지게되는데 재귀를 이용하면 50번째 근처만 가도 굉장히 오래걸리게 됩니다. 즉, 시간 효율이 굉장히 안좋기 때문에 10만번째의 수까지 재귀로 구한다는건 이미 아니란걸 어느정도 유추할 수 있습니다.

 

피보나치를 재귀로 풀어가는 과정에 대한 블로그를 참고해보면 조금 더 쉽게 알 수 있습니다.

https://velog.io/@beton/문제풀이재귀함수의-형태로-피보나치-수열-구하기

[문제풀이]재귀함수의 형태로 피보나치 수열 구하기

 

해당 블로그에서 n을 5로 가정했을 때 아래와 같은 그림으로 재귀함수가 진행된다고 설명합니다. 잘 보시면 아시겠지만 중복된 계산과정이 굉장히 많습니다. 따라서 재귀는 속도, 효율 보다는 "코드의 간결성" 때문에 쓰는 경우가 많고 재귀를 대략 50번 이상 반복해야 한다면 재귀를 쓰면 안되겠구나. 라는걸 고려할 수 있습니다.

 

재귀를 쓸 때 시간이 얼마나 걸릴지 대략 봤습니다.

재귀로 하는 경우 테스트

public static void main(String[] args) {
        System.out.println(solution2(45));
}
    
public static int solution2(int n) {

        long preTime = System.currentTimeMillis();
        int answer = fibo(n);
        long afterTime = System.currentTimeMillis();
        System.out.println("걸린시간 ms: " + (afterTime - preTime));
        return answer;
}

public static int fibo(int n) {

    if (n==0) return 0;
    if (n==1) return 1;

    return (fibo(n-2) + fibo(n-1))%1234567;
}

위와 같은 코드를 진행했을 때 아래와 같은 결과가 나왔습니다.

n을 45를 주었을 때 6초 가량이 걸렸고 이미 코딩테스트에서는 너무 긴 시간으로 볼 수 있습니다. 재귀 특성상 깊이가 깊어질 때 마다 기하급수적으로 시간복잡도가 증가합니다. 궁금해서 해보니 n이 40일 때는 700ms, n이 50일 때는 121029ms 대략 120초가량 걸렸네요

 

따라서, 해당 문제는 아래와 같이 풀어서 해결했습니다.

 

정답 코드

public static int solution(int n) {
        int[] numArr = new int[n+1];
        numArr[0] = 0;
        numArr[1] = 1;
        for(int i=2; i<=n; i++) {
            numArr[i] = (numArr[i-1] + numArr[i-2]) % 1234567;
        }
        return numArr[n];
    }

위와 같이 해결할 경우 배열을 쓰며 값을 기억해놓기 때문에 중복되는 계산을 매우 줄여 시간복잡도를 줄일 수 있습니다. O(n2) -> O(n)

 

물론, 배열과 재귀함수의 차이보다 메모리를 활용해 값을 기억해두는 메모이제이션을 활용하냐 못하냐가 주된 포인트이기 때문에 재귀함수를 사용하면서도 메모이제이션을 통해 시간복잡도를 줄일수는 있습니다.