C++로 배열에서 나머지 모든 요소의 합과 같은 요소 찾기

이 문제에서는 n개의 양의 정수로 구성된 배열 arr[]가 주어지며, 우리의 과제는 나머지 모든 요소의 합과 같은 값을 가진 요소를 찾는 것입니다.

문제 이해하기: 특정 요소 하나를 제외한 나머지 모든 요소의 합이 그 요소 자체의 값과 정확히 일치하는 경우를 찾아야 합니다.

예제로 문제 이해하기

입력: arr[] = { 5, 4, 17, 1, 7 }

출력: 17

설명 −

나머지 요소들의 합은 (5 + 4 + 1 + 7) = 17이며, 이는 남겨진 요소인 17과 정확히 같습니다. 따라서 정답은 17입니다.

해결 접근 방식 −

이 문제를 해결하는 가장 간단한 방법은 '배열 전체 요소의 합은 조건을 만족하는 해당 요소 값의 두 배와 같다'는 수학적 성질을 활용하는 것입니다. 즉, 어떤 요소 arr[i]가 조건을 만족하려면 다음 식이 성립해야 합니다.

sum = 2 × arr[i]

이 아이디어를 바탕으로 다음 단계를 순서대로 수행합니다.

1단계: 배열의 모든 요소의 합(sum)을 구합니다.
2단계: 배열의 각 요소에 대해 반복문을 실행합니다.

2.1단계: 현재 요소가 (2 × arr[i]) == sum 조건을 만족하는지 확인합니다.

2.1.1단계: 조건이 참이면 flag를 1로 설정하고 반복문을 종료합니다.

2.2.1단계: 조건이 거짓이면 다음 요소로 넘어갑니다.

3단계: flag == 1이면 해당 요소 arr[i]를 출력합니다.
4단계: 그렇지 않다면 "해당 요소를 찾을 수 없습니다"라는 메시지를 출력합니다.

이 알고리즘의 시간 복잡도는 배열을 두 번 순회하므로 O(n)이며, 추가 공간은 상수만 사용하므로 공간 복잡도는 O(1)입니다. 매우 효율적인 해결 방법입니다.

솔루션 동작을 확인하는 프로그램

예제 코드

#include <iostream>
using namespace std;

void findElemenetInArray(int arr[], int n) {
    
    int arraySum = 0;
    int flag = 0, i;
    for (i = 0; i < n; i++)
       arraySum += arr[i];

    for (i = 0; i < n; i++)
       if ( (2*arr[i]) == arraySum ) {
          flag = 1;
          break;
       }
            
    if(flag)
       cout<<arr[i];
    else
       cout<<"No such element is found!";
    
}

int main() {
   int n = 5;
   int arr[n] = { 5, 4, 7, 1, 17 };
   findElemenetInArray(arr, n);
   return 0;
}

실행 결과

17