[ Codility ] MaxProductOfThree - python

개념

Lesson 6. Sorting 두 번째 문제

 

문제요약

입력으로 주어진 정수 배열에서 숫자 3개를 곱한 값 중 최대를 리턴하라

 

첫번째 접근(효율성 고려X)

문제에 충실히 만들수 있는 모든 인덱스 조합을 만들고, 그 조합대로 값을 곱한 뒤 최대일 경우 max-value값을 갱신해주는 코드(3개니까 당연히 3중 for문을 돌고, 시간복잡도는 O(N**3)이상)

def solution(A):
    max_v = A[0]*A[1]*A[2]
    for i in range(len(A)-2):
        for j in range(i+1, len(A)-1):
            for k in range(j+1,len(A)):
                if A[i]*A[j]*A[k]>max_v:
                    max_v = A[i]*A[j]*A[k]
    return max_v

 

두번째 접근(통과한 코드)

기본적으로 세 수를 곱할때 음수와 양수의 조합은 다음과 같다. 여기서 무시한다는건 어차피 음수는 양수보다 클 수 없기 때문에 이 문제를 풀 때 고려하지 않아도 되는 경우라는 의미다.

• 양수 * 양수 * 양수 =  양수
• 음수 * 양수 * 양수 =  음수 (무시)
• 음수 * 음수 * 양수 =  양수
• 음수 * 음수 * 음수 =  음수 (무시)

 

또 우리에게 주어질 수 있는 배열의 조합은 다음과 같다. (회색 글씨는 정렬했을때)

• 모두 음수로 구성된 배열 (맨 뒤 세 수를 곱한 값이 무조건 최대)
• 모두 양수로 구성된 배열 (맨 뒤 세 수를 곱한 값이 무조건 최대)
• 음수와 양수가 뒤섞인 배열 (위의 양수, 음수 조합을 고려해야 함)

 

이 모든 케이스와 각각의 조합을 따지는건 너무 오래걸리고 무의미하다. 조금만 생각해보면 사실 더 생각할 필요없는 간단한 해결방법이 존재한다. 왜냐면 우리는 정렬을 활용하면 되기 때문이다. 따라서 어떤 배열이 들어와도 오름차순 정렬을 시켰다면 두 가지 경우 (1) 맨 뒤의 세 수를 곱한 값 (2) 맨 앞의 두 수와 맨 뒤에 있는 수 한개를 곱한 값 중 하나에서 최대값을 구할 수 있다.

def solution(A):
    A.sort()
    return max(A[0]*A[1]*A[-1],A[-3]*A[-2]*A[-1])