> 문제
배열의 element들 중 특정 값의 왼쪽에 있는 숫자들의 합과 오른쪽에 있는 합이 같을 때 그 숫자를 pivot이라 하고 pivot의 인덱스를 리턴하는 문제입니다.
위와 같은 경우 9의 왼쪽의 element들의 합은 11이고 오른쪽 element들의 합은 11이기 때문에 9는 pivot이 되고 index 3이 리턴됩니다.
위 배열의 경우 pivot이 존재할 수 없고 -1을 리턴하면 정답이 됩니다.
> solution1_brute force
완전탐색 알고리즘을 생각해볼 수 있습니다.
예시와 같이 처음에 8을 기준으로 오른쪽의 숫자들을 더해줍니다.(O(n))
이후 기준을 옮기고 좌 우의 숫자들을 각각 더합니다(O(n) + O(n))
이렇게 계속 진행하면 O(n)*n이 되기 때문에 O(n²)의 time complexity가 됩니다.
더 좋은 방법을 생각해야 합니다.
> solution2_sliding window
전체 합계를 구합니다.(O(n))
전체합계 = 31
8을 pivot으로 잡았다면 전체합계에서 8을 빼줍니다.
전체(오른쪽)합계 = 31 - 8
아직 pivot 왼쪽의 합계는 0입니다.
pivot이 오른쪽으로 이동하고 pivot은 2가 되었습니다.
전체(오른쪽)합계 = 31 - 8 - 2
왼쪽 합계에 이전 pivot이었던 8을 더해줍니다.
왼쪽합계 = 0 + 8
이와 같은 방식으로 pivot이 이동하며 좌•우의 값들을 더하고 빼며 pivot index를 찾아나가게 됩니다.
pivot이 한 번 이동할 때 필요한 계산량은 O(1)이고 총 n개의 pivot이 있으므로 o(n)의 time complexity가 필요하고 맨 처음 전체합계를 한 O(n)까지 총 O(n)으로 array 갯수에 linear한 time complexity를 갖습니다.
▶︎ code
array = [8, 2, 1, 9, 3, 6, 2]
def find_pivot_index(values):
total_sum = sum(values)
left_sum = 0
right_sum = total_sum
past_pivot = 0
for i in range(len(array)):
pivot = values[i]
right_sum = right_sum - pivot
left_sum = left_sum + past_pivot
if left_sum == right_sum:
return i
past_pivot = pivot
return -1
print(f'The index of pivot is {find_pivot_index(array)}')출처: 코드없는 프로그래밍
