[C++][구현] findPivotIndex (배열 슬라이딩 문제)

 

시간복잡도에 대해서 생각해 볼 수 있는 좋은 문제였습니다.

 

배열에서 어느 한 지점(Pivot)을 기준으로 왼쪽의 배열의 합, 오른쪽의 배열의 합이 같으면 그 지점의 pivot index를 알아내는 문제입니다.

 

일단 기본적인 brutal 적인 생각으로는 기준점(pivot)을 정하고, 왼쪽의 합, 오른쪽의 합을 구한다면 시간 복잡도가 O(N^2)가 되어버립니다.

 

더 나은 차선책의 생각을 해본다면,  전체 배열 값을 더하고(O(N)),

기준점을 정하면서,

왼쪽의 배열값은 =  왼쪽 배열값 + 이전피봇값

오른쪽의 배열값은 = 전체배열값 - 이전피봇값

이런식으로 흘러간다면 O(N)의 시간복잡도를 구할 수 있습니다.

 

따라서, 전체배열의 합 O(N) + 기준점을 정하여, 좌우 배열의 합값을 비교하는 식 O(N) = O(2N)  = O(N)이기에

 

O(N)의 시간복잡도를 가지고 슬라이딩 문제를 풀 수 있습니다.

 

// O(n)

#include <iostream>
using namespace std;
 
int findPivotIndex(int nums[], int length) {
	int leftSum(0);
	int rightSum(0);
	
	for (int i = 0; i < length; i++) {
		rightSum += nums[i];
	}

	int pastPivotNum = 0;
	for (int i = 0; i < length; i++) {
		int pivotNum = nums[i];
		leftSum += pastPivotNum;
		rightSum -= pivotNum;

		if (leftSum == rightSum) return i;
		pastPivotNum = pivotNum;
	}

	return -1;
}

 

매번 처리되는 중복된 요소를 버리지 않고, 활용하여 더욱 효율적인 알고리즘을 완성할 수 있다는 점을 배웠습니다.