[Swift 알고리즘] MaxProductOfThree - Codility

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

---

문제 분석

원소 3개를 곱했을 때, 최대가 되는 결과값을 구하라
 N = 100,000이므로 O(N^3)은 불가능
 정렬을 해서 가장 큰 값 3개를 곱하는 것은 반례가 있다
     절댓값이 더 큰 음수 2개를 곱하고, 가장 큰 양수를 곱하는 상황이 있다
     음수를 원소로 사용하려면, 반드시 2개를 곱해야 한다.
     즉 음수를 원소로 사용하려면, 반드시 가장 작은 원소 2개만 가능하다.
         그보다 작은 것은 최댓값이 아니다.
     따라서 가장 큰 양수 3개의 조합과, 가장 작은 음수 2개 + 가장 큰 양수 1개의 조합이 전부.

의사 코드

let size = A.count
 let sortedA = A.sorted() // 오름차순 정렬
 let onlyPositive = sortedA[size - 1] * sortedA[size - 2] * sortedA[size - 3]
 let withNegative = sortedA[0] * sortedA[1] * sortedA[size - 1]
 둘 중에 큰 값을 return

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    let size = A.count
    let sortedA = A.sorted()
    let onlyPositive = sortedA[size - 1] * sortedA[size - 2] * sortedA[size - 3]
    let withNegative = sortedA[0] * sortedA[1] * sortedA[size - 1]

    return onlyPositive > withNegative ? onlyPositive : withNegative
}

추가된 내용

A -> [-8, -7, -6, -5, -4, -3, -2, -1]
onlyPositive -> -6
withNegative -> -56

 

최초 풀이 당시에는 모든 원소가 음수인 케이스를 고려하지 않았지만, 이 경우도 가능하다.

이 케이스에서는 절댓값이 작은 음수 3개를 선택하는 경우가, 가장 큰 값을 반환하기 때문.

변수명은 바꿀 필요가 있겠다. onlyBack / withFront 정도로.