C++로 배열에서 b번 등장하는 유일한 원소 찾기

문제 개요

이 문제에서는 크기가 n인 배열 arr[]와 두 정수 a, b가 주어집니다. 우리의 목표는 정확히 b번 등장하는 유일한 원소를 찾는 것입니다.

배열의 모든 값은 a번씩 나타나지만, 단 하나의 값만 b번 나타납니다. 바로 그 값을 찾아야 합니다.

예제를 통해 문제를 이해해 보겠습니다.

입력:

arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1, 1, 1}, a = 4, b = 3

출력:

5

풀이 접근 방법

가장 단순한 방법은 각 원소의 등장 횟수를 세어 자료구조에 저장한 뒤, 빈도가 b인 값을 찾는 것입니다. 하지만 이 방법의 시간 복잡도는 O(N²)으로 비효율적입니다.

더 효과적인 방법은 수학적 성질을 활용하는 것입니다. 먼저 배열에서 중복을 제거한 고유 원소들의 합을 구하고, 여기에 a를 곱합니다. 그런 다음 배열 전체의 합을 빼고, 그 결과를 (a - b)로 나누면 b번 등장하는 값이 됩니다.

이 공식이 성립하는 이유는 다음과 같습니다. 고유 원소의 합을 S라고 할 때, 모든 원소가 a번씩 나타난다면 총합은 a × S가 됩니다. 그러나 실제 배열에서는 하나의 값 x가 b번만 나타났으므로, 배열의 실제 합은 a × S − (a − b) × x입니다. 따라서 x = (a × S − 배열의 합) / (a − b)라는 식을 유도할 수 있습니다.

구현 예제

다음 프로그램은 위 해결 방법의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
int findbFreqVal(int arr[], int n, int a, int b){
   unordered_set<int> uniqueVal;
   int uniqueValSum = 0, arrSum = 0;
   for (int i = 0; i < n; i++) {
      if (uniqueVal.find(arr[i]) == uniqueVal.end()) {
         uniqueVal.insert(arr[i]);
         uniqueValSum += arr[i];
      }
      arrSum += arr[i];
   }
   uniqueValSum = a * uniqueValSum;
   return ((uniqueValSum - arrSum) / (a - b));
}
int main(){
   int arr[] = { 4, 4, 4, 31, 8, 8, 8, 5, 5, 5};
   int a = 3, b = 1;
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The value of the array that appears b times is "<<findbFreqVal(arr, n, a, b);
   return 0;
}

실행 결과

The value of the array that appears b times is 31

위 코드에서는 unordered_set을 사용해 고유 원소를 추적하면서 동시에 배열 전체의 합을 계산합니다. 이렇게 하면 한 번의 순회(O(N))만으로 답을 구할 수 있어, 단순 카운팅 방식보다 훨씬 효율적입니다.