이 문제에서는 정렬된 고유한 값을 가진 배열 arr이 주어집니다. 우리의 과제는 배열 합계의 절반 값과 동일한 요소가 배열에 존재하는지 확인하는 것입니다.
문제 설명
배열 arr[]에서 배열의 모든 요소 합계가 2*X와 같아지는 요소 X를 찾아야 합니다. 다시 말해, 어떤 요소의 값이 전체 합계의 정확히 절반이 되는지 확인하는 것입니다.
예제로 이해하기
입력: arr[] = {2, 4, 5, 6, 7}
출력: No (존재하지 않음)
설명:
합계 = 2 + 4 + 5 + 6 + 7 = 24
24의 절반은 12이지만, 배열에는 12에 해당하는 요소가 없으므로 조건을 만족하는 요소를 찾을 수 없습니다.
해결 접근 방법
이 문제를 해결하려면 배열의 모든 요소 합계의 절반에 해당하는 값을 가진 요소를 찾으면 됩니다. 배열이 이미 정렬되어 있으므로 이진 탐색(Binary Search) 알고리즘을 활용하면 매우 효율적으로 탐색할 수 있다는 점이 핵심입니다.
알고리즘
- 1단계: 배열의 모든 요소 합계를 계산합니다.
- 2단계: 합계가 홀수라면 -1을 반환합니다. (홀수는 2로 나누어 떨어지지 않으므로 절반 값이 정수가 될 수 없습니다.)
- 3단계: 합계가 짝수라면 x * 2 = sum을 만족하는 요소 x를 이진 탐색으로 찾습니다.
- 4단계: 해당 요소를 찾으면 그 값을 반환합니다.
- 5단계: 찾지 못하면 -1을 반환합니다.
솔루션 구현 예제
#include <iostream>
using namespace std;
int checkForElement(int array[], int n) {
int arrSum = 0;
for (int i = 0; i < n; i++)
arrSum += array[i];
// 합계가 홀수면 절반 값인 요소는 존재할 수 없음
if (arrSum % 2)
return -1;
// 이진 탐색으로 sum/2와 같은 요소 찾기
int start = 0;
int end = n - 1;
while (start <= end)
{
int mid = start + (end - start) / 2;
if ((2 * array[mid]) == arrSum)
return array[mid];
else if ((2 * array[mid]) > arrSum)
end = mid - 1;
else
start = mid + 1;
}
return -1;
}
int main() {
int array[] = { 4, 5, 6, 7, 9 };
int n = sizeof(array) / sizeof(array[0]);
int x = checkForElement(array, n);
if(x != -1)
cout<<"Element found, value is "<<x;
else
cout<<"Element not found!";
return 0;
}출력 결과
Element not found!
위 예제에서 배열 {4, 5, 6, 7, 9}의 합계는 31로 홀수입니다. 따라서 프로그램은 이진 탐색을 수행하기 전에 합계가 홀수임을 확인하고 즉시 -1을 반환하여 "Element not found!" 메시지를 출력합니다. 만약 합계가 짝수였다면 이진 탐색을 통해 sum/2 값과 일치하는 요소를 O(log n) 시간 안에 찾았을 것입니다.
복잡도 분석
시간 복잡도: O(n) — 배열 합계를 계산하는 데 O(n), 이진 탐색에 O(log n)이 소요되므로 전체 시간 복잡도는 O(n)입니다.
공간 복잡도: O(1) — 추가적인 메모리 공간을 사용하지 않는 제자리(in-place) 알고리즘입니다.