[코딜리티] Tape Equilibrium - 시간 복잡도 줄이기

 

▼ 문제 링크

Codility

 

# 풀이 1
내가 처음 푼 문제 풀이

func solution(_ A : inout [Int]) -> Int {
    var left = 0
    var right = 0
    var index = 0
    var result = 0

    for i in 1..<A.count {
        left = 0
        right = 0

        index = i
        repeat {
            index -= 1
            left += A[index]
        } while index > 0

        index = i
        repeat {
            right += A[index]
            index += 1
        } while index < A.count

        if i == 1 {
            result = abs(left-right)
        } else {
            result = (result > abs(left-right) ? abs(left-right) : result)
        }
    }

    return result
}

1. for문으로 1부터 마지막 요소까지를 기준으로 배열을 두 개로 나누고
2. 그 for문 안에서 왼쪽 배열과 오른쪽 배열의 각각의 총합을 구한다.
3. 왼쪽 배열 합과 오른쪽 배열 합의 차를 계산하고
4. 그 결과를 이전 결과와 비교해서 더 작은 값을 반환한다.

위 코드는 로직은 맞았으나 시간 복잡도가 O(N*N)으로 퍼포먼스 테스트에서 타임아웃 에러가 떴다. 🥲

그래서 조금이라도 반복문을 돌리는 횟수를 줄여보려고 발악을 해 본 게 아래 코드

 

 

# 풀이 2
두 개로 나눈 배열의 합의 차는 (전체 합 - 뺄 배열의 합*2)라는 식을 이용한 코드

func solution(_ A : inout [Int]) -> Int {
    var totalSum = 0
    var devidedSum = 0
    var index = 0
    var result = 0
    var absSubtraction = 0

    A.forEach {
        totalSum += $0
    }

    for i in 1..<A.count {
        index = i
        devidedSum = 0
        
        if i <= A.count/2 {
            repeat {
                index -= 1
                devidedSum += A[index]
            } while index > 0
        } else {
            repeat {
                devidedSum += A[index]
                index += 1
            } while index < A.count
        }
        
        absSubtraction = abs(totalSum - devidedSum*2)

        if i == 1 {
            result = absSubtraction
        } else {
            result = (result < absSubtraction ? result : absSubtraction)
        }
    }

    return result
}

전체적인 코드는 풀이 1과 비슷하지만, 여기서는 두 배열의 합을 각각 구하지 않고 한쪽 배열의 합만 구한 뒤 해당 값의 2배를 빼는 방법을 사용했다. 하지만 돌리는 while문 횟수가 아주 조금 줄어들었을 뿐 전체적으로 큰 변화는 없었고, 풀이 1과 마찬가지로 타임아웃 에러를 받았다. 퉤...

대체 시간 복잡도는 어떻게 줄이는데?! 하고 풀이를 찾아다녔고 세상엔 똑똑한 사람들이 참 많다. 사실 풀이를 보고 나면 바로 이해가 가는데 왜 혼자서는 답이 안떠오르는지...🤦

 

 

# 풀이 3
똑똑한 천재들의 풀이 방법 베끼기

func solution(_ A : inout [Int]) -> Int {
    var leftSum = 0
    var rightSum = 0
    A.forEach {
        rightSum += $0
    }
    var difference = 0
    var result = 0

    for i in 1..<A.count {
        leftSum += A[i-1]
        rightSum -= A[i-1]
        difference = abs(leftSum-rightSum)

        if i == 1 {
            result = difference
        } else {
            result = (result > difference ? difference : result)
        }
    }

    return result
}

이전 풀이들과 달리, 굳이 행렬의 합을 while문 안에서 한꺼번에 구할 필요가 없었다! for문 하나만으로도 충분히 두 배열의 합과 그 차를 각각 구할 수 있었고, 시간 복잡도는 O(N)으로 훨씬 줄어들었다. 풀이 1, 2에서는 최대 2.060초가 걸리던 게 0.036초로 어마어마하게 줄었더라...🙃