[python] Codility Lesson 3-3. TapeEquilibrium

Time Complexity section이라 O(N^2)이상 시간복잡도가 나오면 안될거 같아 2중 for문 대신 O(N) 또는 O(NlogN) 알고리즘을 생각 해보았다...

 

알고리즘 공부를 하며, list의 모든 합을 이용한 문제가 꽤 있는 것 같다.. 이번 문제도 list의 총 합을 이용해서 문제를 풀어 보았다.

 

def solution(A):
    # write your code in Python 3.6
    SUM = sum(A)
    answer_list = list()
    first = 0
    second = 0
    for i in range(len(A)-1):
        first += A[i]
        SUM -= A[i]
        second = SUM
        answer_list.append(abs(first - second))
    return min(answer_list)

 

1. first, second 부분으로 나뉘어 계산하는데 그것을 for문 안에서 SUM을 갱신 시키며 값을 할당해 주자.

 

2. answer_list에 테이프 각각의 값을 append하자. 그리고 거기서 최소값을 return 하자.

 

3. 예외 상황은...?  문제 상황에서 empty_list는 없고 list의 최소크기는 2 그리고 element의 int 범위를 보니 큰 문제는 없겠구나.

 

무난한 문제였다!