[Codility] Lesson3. TimeComplexity-TapeEquilibrium C언어 풀이

1. 문제

길이가 N인 배열 A와 정수 P를 주고, 0부터 P-1의 합과 P부터 N까지의 합을 비교하여 가장 적은 차이가 나는 값을 찾는 문제이다. P는 1부터 시작해 N-1까지 차례로 증가한다.

예시   
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3 일 때,

• P = 1, A[0] - (A[1] + A[2] + A[3] + A[4]) = 3 - 10 = 7
• P = 2, (A[0] + A[1]) + (A[2] + A[3] + A[4]) = 4 - 9 = 5
• P = 3, 6 - 7 = 1
• P = 4, 10 - 3 = 7

최소값 인 1을 반환한다.

2. 정답

첫번째 - 100점

int solution(int A[], int N) {
    int sumToP = A[0];
    int sumToN = 0;
    for (int i = 1; i < N; i++) {
        sumToN += A[i];
    }

    int min = abs(sumToP - sumToN);

    for (int i = 2; i < N; i++) {
        sumToP += A[i-1];
        sumToN -= A[i-1];
        
        int diff = abs(sumToP - sumToN);
        if (diff < min) {
            min = diff;
        }
    }
    return min;
}

A[0]값(sumToP)과 나머지 값의 합(sumToN)의 차(min)를 기준값으로 잡는다.
A[1]값에 sumToP를 더해주고 sumToN에서는 빼준 다음 차(diff)를 구한다.
diff가 min보다 작으면 min에 입력한다.