[Swift] Codility Lesson 3 - TapeEquilibrium

문제

A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7

P = 2, difference = |4 − 9| = 5

P = 3, difference = |6 − 7| = 1

P = 4, difference = |10 − 3| = 7

Write a function:

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

that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

For example, given:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3

the function should return 1, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000];

each element of array A is an integer within the range [−1,000..1,000].

 

링크

TapeEquilibrium coding task - Learn to Code - Codility

 

문제 분석

• N개의 정수로 구성된 배열 A가 입력으로 주어진다.
• 배열 A를 정수 P를 기준으로 두 구간으로 나눈다.
• 각 구간 합의 차이가 가장 작을 때, 두 구간 합의 차이를 반환한다.
• |A[0...(P-1) - A[P...(N-1)|  

ex) A = [3, 1, 2, 4, 3]

P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7

두 구간 합의 차이가 가장 작을 때는 P가 3일 때, 값은 1이다.

 

해결방안 1 - 실패

1. 배열 A의 요소가 2개 라면 두 값의 차이를 반환
2. 0부터 P-1까지의 구간합과 P부터 N-1까지의 구간합을 계산해 차이를 계산
3. 이전의 차이 값과 현재의 차이 값 중 더 작은 값을 변수에 저장
4. 2,3번 과정을 P를 1부터 (N-1)까지 증가시키며 반복 

Solution 1

public func solution(_ A : inout [Int]) -> Int {
    if A.count == 2{
        return abs(A[0]-A[1])
    }
    var re = Int.max
    
    for P in (1..<A.count){
        let sum = abs(A[0...P-1].reduce(0, +) - A[P...A.count-1].reduce(0, +))
        re = min(sum, re)
    }
    return re
}

• 배열의 크기가 큰 경우 timeout 오류 발생
• 시간 복잡도: O(N * N)

 

해결방안 2 - 성공

1. 배열 A의 요소가 2개 라면 두 값의 차이를 반환
2. front 변수를 선언하여 0으로 초기화하고, back 변수를 선언하여 배열 A의 요소들의 총합을 계산하여 저장
3. 배열 A의 요소들을 0번 요소부터 N-2까지 순서대로 계산
   1. front 변수에는 현재 index의 요소 값을 플러스
   2. back 변수에서는 현재 index의 요소 값을 마이너스
   3. 둘의 차이를 구한 후 이전의 계산 값과 현재의 계산 값 중 더 작은 수를 변수에 저장

Solution 2

public func solution(_ A : inout [Int]) -> Int {
    if A.count == 2{
        return abs(A[0] - A[1])
    }
    
    var front = 0, back = A.reduce(0, +)
    var re = Int.max
    
    for (index, num) in A.enumerated() {
        front += num
        back -= num
        let diff = abs(front - back)
         
        if index == A.count - 1 {
            break
        } else {
            re = min(re, diff)
        }
    }
    return re
}

• 시간 복잡도: O(N)