가장 큰 곱 만들기 문제

문제

주어진 정수 배열 number에는 50개 미만의 1보다 크고 1000보다 작은 정수가 주어져 있다. 이 중 단 하나의 숫자에 +1 하여 전체 숫자의 곱을 가장 크게 만든 뒤 그 곱을 리턴하라.

입력예시

numbers = {1, 2, 3}

return : 12

numbers = {1, 3, 2, 1, 1, 3}

return : 36

풀이

가장 쉽게 떠올릴 수 있는 풀이는 먼저 배열의 모든 원소의 곱을 구한 뒤, 전체 배열을 순회하며 그 배열의 숫자를 나눈뒤 다시 1을 더한 숫자로 곱해 보며 최대값을 찾는 것이다. 시간 복잡도는 O(N)으로 매우 짧지만 이 문제는 약간의 수학적 센스를 발휘하면 조금 더 쉬워진다. 

+1 을 하여 전체의 곱을 가장 크게 만드는 숫자는 배열에서 가장 작은 숫자이다. 어떤 숫자 n을 +1 할때 전체 곱의 변화는 항상 (n+1)/n 이기 때문에 n값이 작을 수록 더 큰 변화가 생긴다. 이 아이디어를 가지고 짠 코드는 역시 O(N)이지만 위의 아이디어보다 반복문을 한 번 덜 돈다. 코드는 다음과 같다.

    public long maxProd(int[] numbers) {
        
        long ret = 1;
        int min = numbers[0];
        
        for (int n : numbers) {
            ret *= n;
            if (min > n) min = n;
        }
        
        ret /= min;
        ret *= min+1;
        
        return ret;
    }