요소가 거의 없는 배열 A가 있다고 가정합니다. 배열에 있는 모든 개별 요소의 합을 찾아야 합니다. 따라서 A =[5, 12, 63, 5, 33, 47, 12, 63]이면 개별 요소의 합은 160입니다. 중복 요소는 일단 고려하면 무시됩니다.
이 문제를 효율적으로 해결하기 위해 순서 없는 집합을 사용할 수 있습니다. 우리는 하나의 for 루프를 실행하고 어떤 값이 처음에 오는지, 합 변수에 추가하고 다음 번에는 이 값을 사용하지 않을 해시 테이블에 저장합니다.
예시
#include<iostream> #include<unordered_set> using namespace std; int getNonRepeatSum(int arr[],int n) { int sum = 0; unordered_set< int > u_set; for (int i=0; i<n; i++) { if (u_set.find(arr[i]) == u_set.end()) { sum += arr[i]; u_set.insert(arr[i]); } } return sum; } int main() { int arr[] = {5, 12, 63, 5, 33, 47, 12, 63}; int n = sizeof(arr)/sizeof(int); cout << "Sum is: " << getNonRepeatSum(arr, n); }
출력
Sum is: 160