티스토리 뷰

728x90
반응형


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


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

}


728x90
반응형

'💻 > CS' 카테고리의 다른 글

codility 3-3. TapeEquilibrium 문제의 시간복잡도를 줄여보자  (0) 2018.11.26
재밌는 ^ (xor) operator  (0) 2018.11.23
댓글
댓글쓰기 폼