MaxProductOfThree

https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/

MaxProductOfThree coding task - Learn to Code - Codility

A non-empty array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).

For example, array A such that:

A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6

contains the following example triplets:

• (0, 1, 2), product is −3 * 1 * 2 = −6
• (1, 2, 4), product is 1 * 2 * 5 = 10
• (2, 4, 5), product is 2 * 5 * 6 = 60

Your goal is to find the maximal product of any triplet.

Write a function:

def solution(A)

that, given a non-empty array A, returns the value of the maximal product of any triplet.

For example, given array A such that:

A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6

the function should return 60, as the product of triplet (2, 4, 5) is maximal.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [3..100,000];
• each element of array A is an integer within the range [−1,000..1,000]

이번에도 다른 플랫폼 문제를 가져와봤다.

 

머릿속으로는 대충 이해가 가는데, 막상 풀려고 하니 째끔 막막한 문제

 

알고리즘을 Efficient하게 짜라는 것이 핵심이다.

 

1. Python

 

진짜 부끄럽지만 Naive한 방법밖에 떠오르지가 않는다.

 

맥락상 Recursive하게 풀어야 할 거 같은데 도대체 우찌 하냔 말이다..ㅠㅠ

 

-- NAIVE;;

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A) -> int: 
    # Implement your solution here
    
    # Naive way
    n = len(A)
    ans = float('-inf')
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                ans = max(A[i]*A[j]*A[k],ans)
    return ans

for문 3개 => O(N**3) WORST ㅠㅠ

 

답지를 봤는데, 뭔가 알고리즘 적으로 푼 건 아닌데.. 모범답안 스럽게 잘 만들었다.

 

def solution(A):
    # 배열을 오름차순으로 정렬
    A.sort()
    
    # 첫 번째 경우: 가장 큰 세 개의 값의 곱
    max_product1 = A[-1] * A[-2] * A[-3]
    
    # 두 번째 경우: 가장 작은 두 개의 값과 가장 큰 값의 곱
    max_product2 = A[0] * A[1] * A[-1]
    
    # 두 경우 중 최대값을 반환
    return max(max_product1, max_product2)

Detected time complexity:

O(N * log(N))

 

효율적이긴 한데, 이렇게 푸는 거 맞나?? 아 맞네. max_product2의 경우 마지막에 A[-1]을 곱해주는구나..

 

발칙한 방법이다..

 

그래도 divide and conquer로 접근해보자!

 

미친길이의 코드가 나온다..

 

def max_cross_product(A, low, mid, high):
    # 왼쪽에서 가장 큰 두 개의 값을 찾기
    left_max1, left_max2 = float('-inf'), float('-inf')
    for i in range(low, mid + 1):
        if A[i] > left_max1:
            left_max2 = left_max1
            left_max1 = A[i]
        elif A[i] > left_max2:
            left_max2 = A[i]
    
    # 오른쪽에서 가장 큰 값을 찾기
    right_max = float('-inf')
    for i in range(mid + 1, high + 1):
        if A[i] > right_max:
            right_max = A[i]
    
    return left_max1 * left_max2 * right_max

def max_triplet_product(A, low, high):
    if high - low + 1 == 3:  # 기본 케이스: 세 개의 요소만 있을 때
        return A[low] * A[low + 1] * A[high]
    
    if high - low + 1 < 3:  # 요소가 3개 미만일 때
        return float('-inf')
    
    mid = (low + high) // 2
    # 왼쪽과 오른쪽의 최대 곱을 재귀적으로 찾음
    left_max = max_triplet_product(A, low, mid)
    right_max = max_triplet_product(A, mid + 1, high)
    
    # 경계에서의 최대 곱을 계산
    cross_max = max_cross_product(A, low, mid, high)
    
    return max(left_max, right_max, cross_max)

def solution(A):
    return max_triplet_product(A, 0, len(A) - 1)

 

이건 C에서 한 번 구현해보자..!

 

 

2. C - Divide and conquer 쓰기

 

겁나리 비효율적이다..;; 아오 결국 cross 구하는 부분에서 N**3을 2번이나 쓴다 ㅋㅋ;;

#include <limits.h>

// 두 구간에 걸친 최대 곱을 찾는 함수
int findCrossingProduct(int A[], int low, int mid, int high) {
    int maxProduct = INT_MIN;
    
    // 왼쪽 구간에서 2개, 오른쪽에서 1개를 선택하는 경우
    for (int i = low; i <= mid; i++) {
        for (int j = i + 1; j <= mid; j++) {
            for (int k = mid + 1; k <= high; k++) {
                int product = A[i] * A[j] * A[k];
                if (product > maxProduct) {
                    maxProduct = product;
                }
            }
        }
    }
    
    // 왼쪽 구간에서 1개, 오른쪽에서 2개를 선택하는 경우
    for (int i = low; i <= mid; i++) {
        for (int j = mid + 1; j <= high; j++) {
            for (int k = j + 1; k <= high; k++) {
                int product = A[i] * A[j] * A[k];
                if (product > maxProduct) {
                    maxProduct = product;
                }
            }
        }
    }
    
    return maxProduct;
}

int maxProductDC(int A[], int low, int high) {
    // 기저 조건: 구간의 길이가 3인 경우
    if (high - low + 1 == 3) {
        return A[low] * A[low + 1] * A[low + 2];
    }
    // 구간의 길이가 3보다 작은 경우 처리
    if (high - low + 1 < 3) {
        return INT_MIN;
    }
    
    int mid = (low + high) / 2;
    
    // 1. 왼쪽 구간의 최대 곱
    int leftProduct = maxProductDC(A, low, mid);
    
    // 2. 오른쪽 구간의 최대 곱
    int rightProduct = maxProductDC(A, mid + 1, high);
    
    // 3. 경계를 걸쳐 있는 경우의 최대 곱
    int crossProduct = findCrossingProduct(A, low, mid, high);
    
    // 세 가지 경우 중 최대값 반환
    int maxProduct = leftProduct;
    if (rightProduct > maxProduct) maxProduct = rightProduct;
    if (crossProduct > maxProduct) maxProduct = crossProduct;
    
    return maxProduct;
}

int solution(int A[], int N) {
    if (N < 3) return 0;  // 배열 길이가 3 미만인 경우 처리
    return maxProductDC(A, 0, N - 1);
}

 

3. C++ 얌생이 기법 쓰기

 

// you can use includes, for example:
#include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // Implement your solution here
    int n = A.size();
    std::sort(A.begin(),A.end());

    return max(A[n-1]*A[n-2]*A[n-3],A[0]*A[1]*A[n-1]);

}