임의의 크기를 가진 정수형 요소 배열이 주어졌을 때, 첫 번째 배열에는 존재하지만 두 번째 배열에는 없는 요소의 개수를 계산하는 것이 이 글의 목표입니다.
배열(array)은 동일한 자료형의 요소들을 고정된 크기로 순차적으로 저장할 수 있는 기본적인 자료구조입니다. 배열은 데이터 집합을 저장하는 용도로 사용되지만, 실제로는 같은 타입의 변수들이 모인 컬렉션으로 이해하면 훨씬 직관적입니다.
예시
입력 − int arr_1[] = {1, 2, 3, 4}
int arr_2[] = {1, 5, 6, 7, 8}
출력 − 개수는 3
설명 − arr_1에는 1, 2, 3, 4가 있고 arr_2에는 1, 5, 6, 7, 8이 있습니다. 요소 1은 두 배열 모두에 존재하므로 제외되며, 결과적으로 개수는 3이 됩니다.
입력 − int arr_1[] = {10, 20, 30, 40, 50}
int arr_2[] = {10, 20, 30, 60}
출력 − 개수는 2
설명 − arr_1에는 10, 20, 30, 40, 50이 있고 arr_2에는 10, 20, 30, 60이 있습니다. 요소 10, 20, 30은 두 배열 모두에 존재하므로 제외되며, 결과적으로 개수는 2가 됩니다.
프로그램에서 사용된 접근 방식
arr_1[]과 arr_2[]라는 두 개의 배열을 생성합니다.
sizeof 연산자를 활용해 두 배열의 길이를 계산합니다. 이 값은 배열에 포함된 요소 수에 해당하는 정수입니다.
첫 번째 배열에만 존재하는 요소의 개수를 저장할 임시 변수(result)를 준비합니다.
요소의 빈도를 저장하기 위해 up이라는 이름의 unordered_map을 생성합니다.
i가 0부터 arr_1의 크기 미만일 때까지 반복문을 실행하며, 매번 up[arr_1[i]] 값을 1씩 증가시켜 각 요소의 빈도를 기록합니다.
i가 0부터 arr_2의 크기 미만일 때까지 또 다른 반복문을 실행합니다.
반복문 안에서 up.find(arr_2[i]) != up.end() && up[arr_2[i]] != 0 조건을 검사하고, 조건이 참이면 up[arr_2[i]] 값을 1 감소시킵니다. 이는 두 배열에서 공통으로 등장한 요소의 빈도를 하나씩 차감하는 과정입니다.
마지막으로 i가 0부터 arr_1의 크기 미만일 때까지 반복하면서 up[arr_1[i]] != 0인 경우를 찾습니다.
빈도가 남아 있는 요소라면 개수를 1 증가시키고, 중복 계산을 방지하기 위해 up[arr_1[i]] = 0으로 설정합니다.
최종 개수를 반환하고 결과를 출력합니다.
예제 코드
#include <iostream>
#include<unordered_map>
using namespace std;
int elements_count(int arr_1[], int arr_2[], int m, int n){
bool f = false;
int result = 0;
// a 배열에 있는 요소들의 빈도를 저장하는 맵
unordered_map<int, int> up;
for (int i = 0; i < m; i++){
up[arr_1[i]]++;
}
// b의 요소가 맵에 존재하는지 확인 후 빈도 차감
for (int i = 0; i < n; i++)
if (up.find(arr_2[i]) != up.end() && up[arr_2[i]] != 0){
up[arr_2[i]]--;
}
// 빈도가 남아 있는 a의 요소 개수 세기
for (int i = 0; i < m; i++) {
if (up[arr_1[i]] != 0){
result++;
up[arr_1[i]] = 0;
}
}
return result;
}
// 메인 함수
int main(){
int arr_1[] = { 2, 4, 4, 6, 6, 6, 8, 9 };
int arr_2[] = { 2, 2, 4, 6, 6 };
int m = sizeof(arr_1)/sizeof(arr_1[0]);
int n = sizeof(arr_2)/sizeof(arr_2[0]);
cout <<"count is "<<elements_count(arr_1, arr_2, m, n);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다 −
count is 4
결과 분석 − arr_1 = {2, 4, 4, 6, 6, 6, 8, 9}의 빈도는 2→1, 4→2, 6→3, 8→1, 9→1입니다. arr_2 = {2, 2, 4, 6, 6}와 비교하면 2는 1회, 4는 1회, 6은 2회 차감됩니다. 그러면 4→1, 6→1, 8→1, 9→1만 남으므로, 첫 번째 배열에만 (중복을 제외하고) 존재하는 요소는 4, 6, 8, 9의 네 가지이며 최종 개수는 4가 됩니다.
이 알고리즘은 해시 기반의 unordered_map을 사용하기 때문에 평균적으로 O(m + n)의 시간 복잡도로 동작합니다. 여기서 m과 n은 각각 두 배열의 크기입니다. 단순 이중 반복문을 사용하는 O(m × n) 방식보다 훨씬 효율적이므로, 배열의 크기가 클수록 이 접근 방식이 유리합니다.