배열 A에 여러 개의 요소가 저장되어 있다고 가정해 보겠습니다. 우리가 구해야 할 것은 배열에 존재하는 모든 고유한(distinct) 요소들의 합입니다. 예를 들어 A = [5, 12, 63, 5, 33, 47, 12, 63]이라면, 고유한 요소들의 합은 160이 됩니다. 중복된 값은 한 번이라도 계산에 포함되었다면 이후에는 완전히 무시됩니다.
접근 방법: unordered_set 활용
이 문제는 unordered_set(정렬되지 않은 집합)을 사용하면 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열을 단 한 번의 반복문(for loop)으로 순회합니다.
- 현재 값이 처음 등장하는 값이라면 합계 변수(sum)에 더하고, 해시 테이블 역할을 하는 집합(set)에 해당 값을 저장합니다.
- 이후 같은 값이 다시 나타나면 집합에 이미 존재하므로 합산하지 않고 건너뜁니다.
알고리즘 단계
- 합계를 저장할 변수
sum을 0으로 초기화합니다. - 빈
unordered_set을 하나 생성합니다. - 배열의 각 요소를 순회하면서, 해당 요소가 집합에 없으면
sum에 더하고 집합에 삽입합니다. - 순회가 끝나면
sum을 반환합니다.
이 방식의 시간 복잡도는 O(n)이며, 해시 기반 자료구조 덕분에 각 요소의 존재 여부 확인과 삽입이 평균적으로 상수 시간(O(1))에 이루어집니다. 추가로 사용되는 공간 복잡도는 O(n)입니다.
예제 코드
#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
코드 설명
getNonRepeatSum 함수는 배열과 배열의 크기를 인자로 받습니다. 내부에서 u_set.find(arr[i])를 호출하여 현재 요소가 집합에 존재하는지 검사하고, 반환값이 end()와 같다면 해당 값이 아직 등장하지 않았음을 의미합니다. 이 경우에만 합계에 더하고 집합에 추가함으로써, 중복 값이 두 번 이상 더해지는 것을 방지합니다.
위 예제에서 5, 12, 63은 각각 두 번씩 등장하지만 첫 번째 등장 시에만 합산되므로, 최종 결과는 5 + 12 + 63 + 33 + 47 = 160이 됩니다.