[Swift 알고리즘] Codility lesson3 - TapeEquilibrium

안녕하세요 코코종입니다.

이번엔 Time Complexity의 마지막 문제입니다.

 

간단하게 문제 설명을 하자면 [Int]의 중간을 잘라서 좌, 우 각각의 합을 비교했을 때 가장 적은 차이(절댓값)를 구하는 것입니다.

처음에 살짝 잘못 이해했던것이 원소 사이의 지점이 아니라 원소자체를 기준으로 한다고 오해해서 쬐금 꼬였습니다.(문제 잘 좀 읽자)

 

N번 만큼 돌면서 좌 우의 배열의 합을 또 계~~~속 구해버리면 N**2가 되어버려서 시간복잡도가 너무 높아집니다.

그래서 stack구조를 활용해서 앞에서부터 더한 값의 배열, 뒤에서부터 더한값의 배열을 저장하고, 이 두 배열의 차를 구하는 아이디어를 떠올렸습니다.

dif에 두 배열의 차를 저장하고 그중 가장 작은 값을 return 해줬습니다.

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")
public func solution(_ A : inout [Int]) -> Int {
    var fromStart: [Int] = []
    var fromEnd: [Int] = []
    var dif: [Int] = []
    
    A.forEach { 
        let start = (fromStart.last ?? 0) + $0
        fromStart.append(start)
    }

    A.reversed().forEach {
        let end = (fromEnd.last ?? 0) + $0
        fromEnd.append(end)
    }
    
    // print(fromStart)
    // print(fromEnd)
    for i in 0..<fromStart.count - 1 {
        var result = fromStart[i] - fromEnd[fromStart.count - i - 2]
        if result < 0 {
            result = 0 - result
        }
        dif.append(result)
    }
    // print(dif)
    return dif.min()!
}

아이디어 자체는 어렵지 않았는데 문제를 살짝 잘못이해했고, 배열의 인덱스가 갑자기 헷갈려서 쬐금 삽질을 했습니다.(잘못이해한 스노우볼)

또한 절댓값은 abs(N)을 사용해도 되지만 result가 음수일때의 조건문으로 처리했습니다.