Codility - Tape_Equilibrium[Python]

😅 문제 

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

🤔 문제 상황 

- 리스트를 긴 테이프라고 생각하여 왼쪽, 오른쪽으로 나눈다. 기준점 P를 중심으로 왼쪽의 총 합과 오른쪽의 총합 차이가 가장 작은 경우를 찾는다.

 

- 리스트를 스캔하며 기준점을 정하는 이중 for문을 사용하였더니 무려 O(N*N)의 말도 안되는 속도가 나왔다..

 

- sum 함수 역시 내부적으로 스캔이 필요하므로 for문 안에 sum 을 쓰면 이중 for문의 효과가 난다. ==> 속도 이슈 발생

 

- 아무리 생각하여도 생각이 안나 다른 사람의 코드를 참고하였다.

 

🧐 해결 전략 

- 양쪽의 총 합을 이미 구해놓고, 기준점만 정하며 오른쪽에서 빼나가고 왼쪽에 더해주는 방법으로 구한다.

 

- 예전에 학습한 방향키 커서 문제에서 스택 2개를 만들어 방향키가 오른쪽이면 오른쪽 항목을 왼쪽으로 push 해주는 것처럼 생각하면 된다.

🎰 코드 

def solution(A):
    right = sum(A[1:])
    left = A[0]
    minv = abs(right - left)
    for i in range(1, len(A)-1):
        right -= A[i]
        left += A[i]
        if minv > abs(right-left):
            minv = abs(right-left)
    return minv

 

🧙‍♂️ 해설

 

- 원래는 시작을 right = sum(A), left = 0 으로 시작했는데 이렇게 하니까 오류가 발생했다. 아마 한쪽으로 쏠리는 경우가 배제되서 문제가 발생한것 같다. 그래서 i의 조건도 len(A)까지로 설정하면 실제로 len(A)-1, 즉 끝까지 도는데 그럼 마찬가지로 반대로 한쪽으로 쏠려 문제가 발생해 반드시 len(A)-1 로 해주어야한다. 

📈 새로 학습한 것 & 실수 

- 총 합을 계산한다고 습관적으로 sum부터 생각했다. 답을 구하는 것 뿐만 아니라 효율적인 방법을 생각하는데 꼭 DP 처럼 어려운 개념만 있는게 아니다. 구현 아이디어로 속도를 증가시킬 수 있다. 

 

- 부분으로 묶는 문제는 하나씩 옮기는 아이디어를 꼭 기억하자!