[코딜리티] MaxDoubleSliceSum

 

▼ 문제 링크

MaxDoubleSliceSum coding task - Learn to Code - Codility

 

문제를 간단하게 정리하면 다음과 같다.

변수 X, Y, Z의 범위: 0 ≤ X < Y < Z < N(배열의 개수)
(X, Y, Z)를 이용한 배열의 더블 슬라이스의 합: A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1]

일 때, 이 더블 슬라이스의 합이 가질 수 있는 모든 경우의 수 중 최대값을 구하라

 

# 풀이 1
변수가 3개니까 for문도 3개!

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var maxResult = 0

    for X in 0..<A.count-2 {
        for Y in X+1..<A.count-1 {
            for Z in Y+1..<A.count {
                maxResult = max(maxResult, A[X+1...Z-1].reduce(0){$0+$1} - A[Y])
            }
        }
    }

    return maxResult
}

가장 처음 시도한 방법.
세 변수의 조건을 가지고 세 번의 for문을 돌려 모든 경우의 수를 찾아낸 뒤, 가장 큰 값만 maxResult에 담는다.

정답은 맞았지만, 시간 복잡도가 O(N**3)가 나와 장렬히 실패! (for문이 3개니까 당연히...🙃)

 

 

# 풀이 2
총합에서 빼는 값이 최소가 되면 되겠지...?!

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var maxResult = 0

    for X in 0..<A.count-2 {
        for Z in X+2..<A.count {
            maxResult = max(maxResult, A[X+1...Z-1].reduce(0){$0+$1} - A[X+1...Z-1].min()!)
        }
    }
    
    return maxResult
}

풀이 1과 비슷한데 변수 Y값과 관련된 for문 하나를 없앨 수 있었다.

'총합이 가장 큰 값을 구하려면 당연히 총합에서 빼는 값이 최소일 때가 가장 큰 값이겠지.' 라는 생각에서 나온 코드.
배열 A[X+1~Z-1] 중에서 가장 작은 값을 가진 요소를 찾아 총합에서 빼줬다.

시간 복잡도가 줄긴 줄었지만(O(N**3) -> O(N**2)), 여전히 결과는 타임 아웃.

여기서 더 끌어봤자 시간만 낭비하고 답은 못찾을 거 같아서 결국 또 집단 지성에 헬프 침

 

 

# 풀이 3
배열에 각 범위의 합 입력하기

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var leftSum = Array(repeating: 0, count: A.count)
    var rightSum = Array(repeating: 0, count: A.count)
    var result = 0
	
    // Y의 좌측 합
    for i in 1..<A.count-1 {
        leftSum[i] = max(0, leftSum[i-1] + A[i])
    }

	// Y의 우측 합
    for i in (1..<A.count-1).reversed() {
        rightSum[i] = max(0, rightSum[i+1] + A[i])
    }

	// A[X+1...Z-1] - A[Y] = A[X+1...Y-1] + A[Y+1...Z-1]
    for i in 1..<A.count-1 {
        result = max(result, leftSum[i-1] + rightSum[i+1])
    }

    return result
}

O(N)의 시간 복잡도를 가진 풀이법.

1. 변수 Y를 기준으로 Y의 왼쪽에 있는 요소들의 합을 구해 leftSum배열에 입력
2. 변수 Y를 기준으로 Y의 오른쪽에 있는 요소들의 합을 구해 rightSum배열에 입력
3. 변수 Y의 왼쪽 합 + 변수 Y의 오른쪽 합을 더해 가장 큰 값을 결과값으로 반환

A[X+1...Z-1] - A[Y] = A[X+1...Y-1] + A[Y+1...Z-1] 라는 걸 이용한 코드다.

처음에는 요소들의 합을 배열로 구하는 게 잘 이해가 가지 않았음

A = [3, 2, 6, -1, 4, 5, -1, 2] 일 때 좌측, 우측 합 두 배열의 값은 각각 다음과 같음
leftSum = [0, 2, 8, 7, 11, 16, 15, 0]
rightSum = [0, 16, 14, 8, 9, 5, 0, 0]

(A[X+1...Z-1] 니까 X의 값과 Z의 값은 포함되지 않음. 그래서 for문도 1부터 A.count-2까지 돌림)

즉, leftSum에서 각각의 요소는 왼쪽에서부터 오른쪽으로 각 요소를 더한 누적값이 된다. (rightSum은 반대 방향)

그리고 여기서 max(0, ~~) 최대값을 구할 때 0과 비교하는 이유는 만약 누적값이 음수가 되면 이전에 계산했던 값들은 그냥 사용하지 않겠다는 의미. rightSum[6]이 -1이 아니라 0인 이유. 배열로 보면 우리가 자연스럽게 X와 Z값을 1:1대칭으로 보게 되는데, 원래 문제의 목표는 '모든 경우의 수 중 최대값을 구하는 것'이니까... 여기서는 Z값을 줄인게 된다. (말이 이상한데 뭐라고 표현해야 할지 모르겠다)

leftSum(i-1) = A[X+1...Y-1]의 합
rightSum(i+1) = A[Y+1...Z-1]의 합

 

배열로 누적값을 입력하는 것, max값을 구할 때 0보다 작은 음수는 0으로 대체하는 것. 이 두 가지에서 이해하느라 고전했다 ㅠ

나는 언제쯤... 집단 지성에 내 힘을 보탤 수 있으려나...