[Codility - Arrays] TapeEquilibrium

https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

TapeEquilibrium coding task - Learn to Code - Codility

- Array의 element 최대 수는 200,000이다. 따라서, O(N^2)의 풀이법을 하면 당연히 시간초과가 날 것이다.

function solution(A) {
    let answer = Number.MAX_SAFE_INTEGER
    for(let i = 0; i < A.length; i++){
        let candid = 0;
        for(let j = 0; j <= i; j++){
            candid += A[j]
        }
        for(let j = i+1; j < A.length; j++){
            candid -= A[j]
        }
        answer = Math.min(answer, Math.abs(candid))
    }
    return answer
}

 

- 처음엔, 이리 저리 꼬아서 생각하다가 시간복잡도 신경쓰지 않고 풀어보기로 했고, 결국 Time out이 떴다.

 

- 곰곰히 생각하던 중, 전에 sliding window를 공부했던 기억이 나서, 이를 활용 해 보기로 했다.

 

function solution(A) {
    let firstNum = A[0]
    let secondNum = 0
    for(let i  = 1; i < A.length; i++){
        secondNum += A[i]
    }
    let answer = Math.abs(firstNum - secondNum)
    for(let i = 1; i < A.length-1; i++){
        firstNum += A[i]
        secondNum -= A[i]
        answer = Math.min(answer, Math.abs(firstNum - secondNum))
    }
    return answer
}

 

- 초기값은 처음 element 단 1개와, 나머지 모든 element들의 합으로 시작한다.

- 이후 element들을 순서대로 순회하면서 firstNum에는 해당 element를 더해주고, secondNum에는 해당 element를 빼주면 O(N)으로 풀어낼 수 있게 된다.