codility 3-3. TapeEquilibrium 문제의 시간복잡도를 줄여보자

처음에 이 문제를 만났을 때는 

public func solution(_ A : inout [Int]) -> Int {

    

    var left = 0

    var right = 0

    

    var difference = 0

    

    for (index,item) in A.enumerated(){

        

        if index == A.count - 1{break}

        

        left += item

        right = A[index+1...A.count-1].reduce(0, +)

        

        if index == 0{

            difference = abs(left-right)

        } else if abs(left-right) < difference{

            difference = abs(left-right)

        }

    }

    

    return difference

}

이렇게 풀었다 

그랬더니 시간복잡도가  O(N ** 2) 으로 나왔다

배열을 slice하고 reduce로 합을 구하는 부분 때문이다 ( 배열의 총합을 구하는데 O(N)이 드는데, 이 작업을 for문 돌면서 n번하니까 그런것같다 ) 

그래서 배열을 slice하고 reduce로 합을 구하는 부분을 덧셈,뺄셈으로 가능하도록 대체했더니.... 시간복잡도가 O(N)  나왔다 >____< 

조금만 생각을 더 하면 더 효율적인 코드(시간복잡도 수치가 낮은)를 짤 수 있구나 :) 

public func solution(_ A : inout [Int]) -> Int {

    

    var left = 0

    var right = A.reduce(0, +)

    

    var difference = 0

    

    for (index,item) in A.enumerated(){

        

        if index == A.count - 1{break}

        

        left += item

        right -= item

        

        if index == 0{

            difference = abs(left-right)

        } else if abs(left-right) < difference{

            difference = abs(left-right)

        }

    }

    

    return difference

}