0. 문제
비어있지 않은 리스트 A에 N개의 숫자가 있다.(N은 2와 100,000 사이의 숫자)
그리고 0 < P < N 의 조건을 가지는 자연수 P가 있다.
자연수 P에 의해 리스트 A는 이렇게 둘로 나눠지게 된다.
A[0], A[1], ..., A[P − 1]
A[P], A[P + 1], ..., A[N − 1]
이때 |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])| 의 가장 작은 값을 구하라.
1. 답변
처음에 답변은 다 맞췄으나 TimeoutError가 났다.
for p in range(1, len(A)):
diff = abs(sum(A[:p]) - sum(A[p:]))
위와 같이 간지나게 풀었는데...
루프를 돌 때마다 리스트 A의 합을 구하는 건 너무 멍청했다.
이번 기회로 sum()이 꽤 많은 시간을 차지할 수도 있다는 걸 알았다.
어쨌든 아래처럼 고쳤더니 무난히 통과!
def solution(A):
left_sum = A[0]
right_sum = sum(A[1:])
min_diff = abs(left_sum - right_sum)
for i in range(1, len(A)-1):
left_sum += A[i]
right_sum -= A[i]
if abs(left_sum - right_sum) < min_diff:
min_diff = abs(left_sum - right_sum)
return min_diff
더하기 1번과 N번의 차이..
최종 시간복잡도는 O(N)이 나왔다.
'개발 > 알고리즘 문제' 카테고리의 다른 글
| [Codility] PermCheck (0) | 2017.11.09 |
|---|---|
| [Codility] FrogJmp (0) | 2017.11.07 |
| [Codility] TapeEquilibrium (0) | 2017.11.06 |
| [Codility] PermMissingElem (0) | 2017.11.05 |
| [Codility] CyclicRotation (0) | 2017.11.04 |
| [Codility] OddOccurrencesInArray (0) | 2017.11.02 |