Codility lesson3_3 - TapeEquilibrium

요약

벡터 A를 input 받아서 임의의 정수 P를 이용하여 A[0] ~ A[P-1]까지의 합과 A[P] ~ A[N]까지의 합의 차의 절댓값중 가장 적은 차이를 찾아라. P는 1~N이 될 수 있겠죠?

 

아이디어

1. 앞에서 부터 원소를 더해간 front_sum과 뒤에서 부터 원소를 더해온 reverse_sum을 구하여 front_sum[P-1] - reverse_sum[P]를 N만큼 연산하여 가장 적은 차를 구하면 된다.

 

코드

 

int solution(vector<int> &A) {
	// write your code in C++14 (g++ 6.2.0)
	vector<int> frond_sum(A.size());
	vector<int> reverse_sum(A.size());
	int min = 987654321;
	int P = 0;
	for (int i = 0; i < A.size(); i++)
	{
		if (i == 0)
			frond_sum[i] = A[i];
		else
			frond_sum[i] = frond_sum[i - 1] + A[i];
	}
	for (int i = A.size() - 1; i >= 0; i--)
	{
		if (i == A.size()-1)
			reverse_sum[i] = A[i];
		else
			reverse_sum[i] = reverse_sum[i + 1] + A[i];
	}
	for (int i = 1; i < A.size(); i++)
	{
		if (abs(frond_sum[i - 1] - reverse_sum[i]) < min) {
			min = abs(frond_sum[i - 1] - reverse_sum[i]);
		}
	}
	return min;

}

결과는

 

front_sum과 reverse_sum 두개를 꼭 다 구해야할까? 라는 생각이 들어서 고민을 많이 했는데요

front_sum만 구한뒤에 front_sum[N] - 2*front_sum[P]의 식으로 P를 0부터 차례로 증가시켜가며 해를 구하는 방법도 있을 수 있겠더라구요.

예를 들어 a, b, c, d, e를 원소로 가지는 벡터배열에서

(a+b+c+d+e) - 2(a)

(a+b+c+d+e) - 2(a + b)

(a+b+c+d+e) - 2(a + b + c)

이해에 도움이 되셨나요??

 

이런방법도 있다는 것을 참고 하시면 될것 같습니다.