Tape Equilibrium

TapeEquilibrium coding task - Learn to Code - Codility

🤔생각해보기

문제 그대로 단순히 배열을 slice 하는 방식으로 풀었더니 시간복잡도 문제라 그런지 점수가 아주 짜게 나왔다.

그래서 Dynamic programming 으로 풀어보았다.

• 합을 저장해가는 배열을 만들어둔다.
• 그 배열에서 하나씩 꺼내서 연산을 진행하면, 다시 처음부터 합을 구할 필요가 없다.

첫번째 풀이 - Total score 61%

def solution(A):
    result = 0
    dp = [0] * (len(A) - 1)
    dp[0] = A[0]

    for i in range(1, len(A) - 1):
        dp[i] = dp[i - 1] + A[i]

    a = sum(A)
    for j in dp:
        abs1 = abs((a - j) - j)
        if result == 0 or result > abs1:
            result = abs1

    return result

어딘가 예외 요소가 있었는지 전체적으로 점수가 만족스럽지 못했다.

정확하진 않지만 예상되는 부분은 result = 0 이라고 초기화하고 조건문을 진행할 때 제대로 값이 반영이 안되는 것으로 보였다.

조금 더 정확하게 동작하도록 코드를 고쳐봤다.

두번째 풀이 - Total Score 100%

def solution(A):
    result = []
    s = sum(A)
    t = [0] * (len(A) - 1)
    dp = [0] * (len(A) - 1)
    dp[0] = A[0]
    t[0] = s - dp[0]

    for i in range(1, len(A) - 1):
        dp[i] = dp[i - 1] + A[i]
        t[i] = s - dp[i]

    for i in range(len(dp)):
        result.append(abs(dp[i] - t[i]))

    return min(result)

min() 을 사용해서 최소값을 리턴해주는 방식이라 점수를 짜게 줄거라 생각했는데, 이 정도는 허용되는 범위 안인가보다. 최악의 경우 약 100,000개를 검사할텐데 O(N)을 만족할 수 있다면 통과라 보여진다.