[알고리즘/Swift] Codility - TapeEquilibrium
문제
- [Codility] https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/
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.
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].
입력
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.
풀이
이 문제는 time complexity 문제라서 시간 복잡도가 어떻게 하면 작게 나오게 할 수 있을지 고민하면서 문제를 풀었다
배열을 두 개의 배열로 나누어서 첫 번째 배열과 두 번째 배열의 차의 절대값을 비교하는데,
배열의 몇 번째 인덱스에서 두 개의 배열로 나누어야 두 배열의 차의 절대값이 가장 작아지나 찾는 문제였다
처음에는 배열을 i를 1부터 늘려가면서 배열의 i index를 기준으로 앞과 뒤 배열의 차를 비교하는 알고리즘을 작성하였다
var target = abs(sum(arr1) - sum(arr2))
하지만 이 알고리즘은 시간 복잡도가 O(n^2)로 문제에서 요구했던 시간보다 길게 나왔다🥲
그래서 정답 코드에 있는 코드와 같이 먼저 두 개의 수에 초기값 (max1 : 배열의 첫번째 값, max2 : 나머지 배열의 총 합)을 넣어주고
for문을 돌면서 i에 해당하는 원소를 max2에서 빼서 max1에 더해주면서 최솟값과 비교를 하였다
그 결과 시간 복잡도가 O(n)으로 줄어들었다
알게된 점
for문 안에서 배열의 메소드들을 사용할 때에는 시간 복잡도가 대폭 증가하므로 주의하여 사용하여야 한다 밑 코드에서 구현한 함수도 시간 복잡도가 O(n) 이므로 for문 밖에서 사용하도록 유의해서 사용하였다!
public func sum (_ array : Array<Int>) -> Int {
return array.reduce(0,+)
}
코드
import Foundation
import Glibc
public func solution(_ A : inout [Int]) -> Int {
var max1 = A[0]
var max2 = sum(A) - max1
var min = abs(max1 - max2)
for i in 1..<A.count-1{
max1 = max1 + A[i]
max2 = max2 - A[i]
var target = abs(max1-max2)
if min >= target{
min = target
}
}
return min
}
public func sum (_ array : Array<Int>) -> Int {
return array.reduce(0,+)
}