[HackerRank_C] Sherlock and Array

자료구조 복습용 search 문제입니다.

- 문제

www.hackerrank.com/challenges/insertionsort2/problem

Insertion Sort - Part 2 | HackerRank

배열의 원소 중 1개를 축으로 잡고 양쪽 원소의 합이 같으면 "YES"를 출력하고 아니면 "NO" 출력하기

작동하는 원리

---

- 풀이

char* balancedSums(int arr_count, int* arr) {
    int left_sum = 0, right_sum = 0;

    if (arr_count == 1)
        return "YES";

    for (int i = 1; i < arr_count; i++)
        right_sum += arr[i];

    for (int mark = 0; mark < arr_count; mark++) {
        if (left_sum == right_sum)
            return "YES";
        else {
            left_sum += arr[mark];
            right_sum -= arr[mark - 1];
        }
    }

    return "NO";
}

1. arr_count가 1인 경우 무조건 같으므로 "YES"를 return한다.
2. 각 원소가 축이 되는 경우를 생각하여 left_sum과 right_sum을 비교해준다. 역시 두 값이 같을 경우 "YES"를 return한다.
3. 0번째 원소가 축인 경우, 1번째 원소부터 맨 마지막 원소까지 다 더해줘야 한다.
4. 각 원소가 축인 경우마다 새롭게 값을 더하는 경우 시간이 너무 오래걸리므로 해당 순서의 원소가 축인 경우를 계산하고, 0번째가 아니라면 left_sum에 해당 순서의 원소를 더하고 right_sum에 다음 원소의 값을 빼준다. (축이 되는 원소는 더하지 않기 때문)
5. for문을 탈출한 경우 축이 되어 양 변의 합이 같아지는 경우가 없다는 것으로 "NO"를 return한다.

---

- 실행결과

통과!