Codility - MaxProductOfThree

첫 번째 풀이

import Foundation
import Glibc

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

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    let arr = A.sorted()
    return arr[arr.count-1] * arr[arr.count-2] * arr[arr.count-3]
}

아무 생각 없이 그냥 크기순으로 정렬해서 제일 끝에 세 숫자 곱하면 되겠네~ 했는데… [-5, 5, -5, 4] 처럼 음수를 포함한 결과가 최대값인 경우가 숨어 있었다.

두 번째 풀이

import Foundation
import Glibc

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

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    if A.count == 3 {
        return A[0] * A[1] * A[2]
    }

    let negative = A.filter{ $0 < 0 }.sorted(by: >)
    let positive = A.filter{ $0 >= 0 }.sorted(by: >)

    if negative.count < 2 {
        return positive[0] * positive[1] * positive[2]
    }
    if positive.count < 3 {
        return negative[0] * negative[1] * positive[0]
    }

    let num1 = positive[0] * positive[1] * positive[2]
    let num2 = negative[0] * negative[1] * positive[0]

    return max(num1, num2)
}

배열 A 에 음수만 있는 경우를 고려하지 않아서 런타임 에러가 떴다. ㅎㅎ;;

최종 풀이

import Foundation
import Glibc

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

public func solution(_ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    if A.count == 3 {
        return A[0] * A[1] * A[2]
    }

    let negative = A.filter{ $0 < 0 }.sorted(by: <)
    let positive = A.filter{ $0 >= 0 }.sorted(by: >)

    if negative.count < 2 {
        return positive[0] * positive[1] * positive[2]
    }
    if positive.count < 3 {
        if positive.isEmpty {
            return negative[negative.count-1] * negative[negative.count-2] * negative[negative.count-3]
        } else {
            return negative[0] * negative[1] * positive[0]
        }
        
    }

    let num1 = positive[0] * positive[1] * positive[2]
    let num2 = negative[0] * negative[1] * positive[0]

    return max(num1, num2)
}

최댓값을 만드는 후보가 될 수 있는 경우는 크게 음수 2, 양수 1 인 경우와 양수 3 인 경우로 나뉜다.

두 경우를 간단하게 확인하기 위해 배열 A 의 음수와 양수를 각각 다른 배열에 따로 저장한 후 절댓값이 큰 순으로 정렬했다.

그리고 두 경우의 값들을 비교하기 전 코너 케이스들을 검사했다. 이 문제에서 나올 수 있는 코너 케이스는 1. 양수 3 값만 존재하는 경우 , 2. 음수 2 양수 1 값만 존재하는 경우 , 3. 양수 값이 하나도 없는 경우 가 있다.

각 코너 케이스들을 처리한 후에 위의 두 가지 경우 값 중 최댓값을 리턴하면 된다.