C++로 배열 속 숨겨진 숫자(Hidden Number) 찾기

문제 소개

이 문제에서는 n개의 정수로 구성된 배열 arr[]이 주어지며, 우리의 목표는 C++로 배열 속 숨겨진 숫자(Hidden Number)를 찾는 프로그램을 작성하는 것입니다.

숨겨진 숫자란?

배열에서 숨겨진 숫자란, 배열의 모든 요소에서 이 숫자를 뺀 결과값들의 합이 0이 되는 수를 의미합니다.

예제로 문제 이해하기

입력

arr[] = {4, 1, 6, 7, 2}

출력

4

배열의 모든 요소에서 4를 뺀 뒤 그 값을 모두 더해 보면 다음과 같습니다.

= (1 - 4) + (6 - 4) + (7 - 4) + (2 - 4)
= -3 + 2 + 3 - 2 = 0

결과의 합이 0이므로, 이 배열의 숨겨진 숫자는 4임을 확인할 수 있습니다.

해결 접근 방법

이 문제는 수학적 성질을 이용하면 아주 간단하게 풀 수 있습니다. 숨겨진 숫자를 x라고 하면, 모든 요소에서 x를 뺀 값의 합이 0이 되어야 하므로 다음 식이 성립합니다.

(arr[0] - x) + (arr[1] - x) + ... + (arr[n-1] - x) = 0
→ 배열 전체의 합 - (n × x) = 0
→ x = 배열 전체의 합 ÷ n

따라서 해결 방법은 다음과 같습니다.

1. 배열의 모든 요소의 합(sum)을 구합니다.
2. 합을 배열의 요소 개수(n)로 나눕니다.
3. 나눈 값이 정수(나머지가 0)라면 그 값이 곧 숨겨진 숫자입니다.
4. 정수로 나누어떨어지지 않는다면 숨겨진 숫자는 존재하지 않으므로 -1을 반환합니다.

구현 예제 코드

#include <iostream>
using namespace std;

int calcHiddenNumber(int arr[], int n){
    long int sum = 0;
    for(int i = 0; i < n; i++){
        sum = sum + arr[i];
    }
    int hidNum = (sum / n);
    if((hidNum * n) == sum)
        return hidNum;
    else
        return -1;
}

int main() {
    int n = 4;
    int arr[] = { 4, 11, 12, 21 };
    cout<<"배열의 숨겨진 숫자는 "<<calcHiddenNumber(arr, n);
    return 0;
}

출력

배열의 숨겨진 숫자는 12

코드 동작 원리

• calcHiddenNumber() 함수는 먼저 반복문을 통해 배열의 모든 요소를 더하여 sum을 계산합니다.
• 그런 다음 sum / n으로 몫을 구하고, hidNum × n == sum 조건을 검사하여 나누어떨어지는지 확인합니다.
• 조건이 참이면 해당 값이 숨겨진 숫자이므로 그대로 반환하고, 거짓이면 숨겨진 숫자가 없다는 의미로 -1을 반환합니다.

위 예제 배열 {4, 11, 12, 21}의 경우 전체 합은 48이고, 48 ÷ 4 = 12로 나누어떨어지므로 숨겨진 숫자는 12가 됩니다.

시간 복잡도

배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n), 추가 공간은 상수만 사용하므로 공간 복잡도는 O(1)입니다. 매우 효율적인 해결 방법이라고 할 수 있습니다.