[Time Complexity] TapeEquilibrium

알고리즘 태클 열렬히 환영합니다~

지적 부탁드립니다~~

[Time Complexity] TapeEquilibrium

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

N개의 정수로 구성된 배열 A가 주어집니다.

배열 A는 테이프 상의 번호를 나타냅니다.

0 < P < N을 만족하는 정수 P는 아래와 같이 테이프를 두 부분으로 나눕니다:

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]) | 

달리말해서, 첫번째 부분의 합과 두번째 부분의 합 사이의 차를 절대값 취해줍니다.

예를 들어 아래와 같은 배열 A가 있다고 합시다:

A[0] = 3

A[1] = 1

A[2] = 2

A[3] = 4

A[4] = 3

우리는 테이프를 네군데서 자를 수 있습니다.

- P=1 일 때, | 3 - 10 | = 7

- P=2 일 때, | 4 - 9 | = 5

- P=3 일 때, | 6 - 7 | = 1

- P=4 일 때, | 10 - 3 | = 7

아래와 같이 N개의 정수로 구성된 A배열을 처리하는 함수를 작성해 봅시다 :

int solution(int A[], int N);

이 함수는 테이프를 두 부분으로 나누었을 때, 최소의 차이값을 반환합니다.

제약조건

- N은 2~100,000사이의 정수입니다(배열의 길이)

- 배열 A의 각 원소는 -1,000~1,000 사이의 값을 갖습니다.

- 시간 복잡도는 최악의 경우 O(N) 입니다.

- 공간 복잡도는 최악의 경우 O(N) 입니다.

- 배열 A는 수정가능합니다.

C언어 100% 점수 획득 코드

int AbsSubtract(int a, int b)

{

if(a>b) return a-b;

else return b-a;

}

int solution(int A[], int N)

{

int i, sum1, sum2=0;

sum1 = A[0];

for(i=1; i<N; i++){

sum2+=A[i];

}

int result = AbsSubtract(sum1, sum2);

int temp=result;

for(i=1; i<N-1; i++){

sum1+=A[i];

sum2-=A[i];

temp = AbsSubtract(sum1, sum2);

if(temp<result) {

result = temp;

}

}

return result;

}

i) 복잡하게 풀어보기

P를 0부터 N-1까지 늘려보면서, 각 경우에 앞부분의 합 - 뒷부분의 합을 구해볼 수 있겠습니다.

이 경우에는 0~N-1까지 N번의 탐색,

그리고 각 탐색마다 앞 부분의 합과 뒷부분의 합을 구하며 N번의 탐색이 이루어집니다.

때문에 N^2의 시간 복잡도를 갖게 됩니다.

ii) 시간 복잡도 줄이기

합을 매 번 구할 필요없이 P의 위치를 변경할 때 마다, 각 부분의 합을 갱신할 수 있습니다.

뒷부분 가장 앞의 원소를 떼서, 앞부분으로 붙여준다고 생각하시면 될 것 같습니다.

이렇게 처리하면, P를 옮길 때 마다 앞,뒤부분의 합을 N번의 탐색을 통해 새로 구하지 않아도 됩니다.

그렇게 해서 구해진 합을 서로 빼서, 최소값과 비교하여 더 작은 값이 나오면 그 값을 최소값으로 저장합니다.