[codility] Lesson 3 | TapeEquilibrium - 파이썬(Python) | Time Complexity

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

3. Time Complexity lesson - Learn to Code - Codility

코딜리티에서 lesson 3 시간 복잡도 문제를 풀었다.

 

이 문제가 이해하는데 가장 시간을 많이 쓴 것 같다.. 영어로 된 것도 있지만 이 문제를 효율적으로 풀어야 하는 나한테 요구하는게 뭔지 파악을 하기가 힘들었다.

문제 그대로 해석하면 p에 따라 리스트 A가 2개로 나뉘어진다. 첫번째 구간은 A[:P]이며 두번째 구간은 A[P:N-1]이다.

이 두 구간의 총 합의 차이를 구하는 문제이다.

---

 

첫번째 시도 - 실패

def solution(A):

    
    diff = []
    for p in range(1, len(A)) :
        tape1 = A[:p]
        tape2 = A[p:len(A)]
        
        sum1 = sum(tape1)
        sum2 = sum(tape2)
        
        diff.append(abs(sum1 - sum2))
        
    diff = min(diff)

    return diff

문제가 말하는 그대로 코드로 구현했다! 당연히 시간초과였다!

내가 푼 코드는 for문이 tape1과 tape2로 두번 실행돼서 시간 복잡도가 O(N*N)이 나왔다.

 

두번째 시도 - 성공

def solution(A) :
    
    tape1 = 0
    tape2 = sum(A)
    
    diff = []
    
    for p in A :
        tape1 += p
        tape2 -= p
        
        diff.append(abs(tape1 - tape2))
    
    return min(diff[:-1])

다른 사람의 풀이를 참고해서 두번째는 겨우 성공했다..

어떻게 저런 생각을 하는지 정말 신기하다!!!!!

첫번째 구간은 0으로 초기화 한 후에 A의 원소를 차례대로 더한 최종 값이며 두번째 구간은 sum(A)로 초기화한 후에 A의 원소를 차례대로 뺀 최종 값이다.

이렇게 간단하게 위에서 내가 for문을 사용해서 만든 diff가 간단하게 만들어진다니...!

그래서 최종 시간 복잡도는 for문이 한번 수행되었기 때문에 O(N)으로 시간 초과없이 통과했다!!

 

해당 문제를 무작정 구현하는 것 보다 수학적인 의미로 풀어낼 수 있는지 한번 더 고민한다면 무지성 for문을 사용하지 않고 깔끔하게 풀 수 있을 것 같다!

---

해당 문제 풀이 코드

GitHub - YOOHYOJEONG/algorithm_practice: 알고리즘 공부 및 코딩테스트 준비