문제 정의
크기가 같은 두 배열 A[]와 B[]가 주어졌을 때, 동일한 크기의 세 번째 배열을 만드는 것이 과제입니다. 결과 배열에는 두 배열에서 선택한 총 n개의 최대값 요소가 포함되어야 하며, A[]에서 선택한 요소들이 먼저 오고 그다음 B[]에서 선택한 요소들이 각각 원래 배열에서 나타난 순서 그대로 배치되어야 합니다. 또한 두 배열에 공통으로 존재하는 요소가 있다면 결과 배열(res[])에는 한 번만 포함되어야 하고, 이 경우 우선권은 A[]에 주어집니다.
예시
입력 배열이 다음과 같다고 가정해 보겠습니다.
arr1[] = {9, 17, 2, 25, 6}
arr2[] = {17, 4, 8, 10, 1}위 입력에 대한 최종 배열은 다음과 같습니다.
{9, 17, 25, 8, 10}여기서 주목할 점은 요소 17이 두 배열 모두에 존재한다는 것입니다. 공통 요소에는 arr1에 우선권이 주어지므로, 결과 배열에는 17이 한 번만 등장합니다.
알고리즘
- 두 배열의 복사본을 만든 뒤, 복사본을 내림차순으로 정렬합니다.
- 해시(맵)를 활용하여 두 배열에서 서로 중복되지 않는 최대 n개의 요소를 선택합니다. 이때 arr1[]에 우선권을 부여합니다.
- 결과 배열을 빈 벡터로 초기화합니다.
- arr1[]을 처음부터 끝까지 순회하면서 해시에 존재하는 요소만 결과 배열에 복사합니다. 이 단계를 통해 원래 배열의 요소 순서가 그대로 유지됩니다.
- arr2[]에 대해서도 동일한 순회를 반복합니다. 단, 이번에는 arr1[]에 없는 요소만 추가합니다.
예제 코드
이제 위 알고리즘을 실제 C++ 코드로 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void printArray(vector<int> &arr, int n) {
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
void getMaxArray(int *arr1, int *arr2, int n) {
vector<int> temp1(arr1, arr1 + n); vector<int> temp2(arr2, arr2 + n);
sort(temp1.begin(), temp1.end(), greater<int>()); sort(temp2.begin(), temp2.end(), greater<int>());
unordered_map<int, int> m;
int i = 0, j = 0;
while (m.size() < n) {
if (temp1[i] >= temp2[j]) {
m[temp1[i]]++;
++i;
} else {
m[temp2[j]]++;
++j;
}
}
vector<int> result;
for (int i = 0; i < n; ++i) {
if (m.find(arr1[i]) != m.end()) {
result.push_back(arr1[i]);
}
}
for (int i = 0; i < n; ++i) {
if (m.find(arr2[i]) != m.end() && m[arr2[i]] ==1) {
result.push_back(arr2[i]);
}
}
cout << "Final array:\n";
printArray(result, n);
}
int main() {
int arr1[] = {9, 17, 2, 25, 6};
int arr2[] = {17, 4, 8, 10, 1};
int n = sizeof(arr1) / sizeof(arr1[0]);
getMaxArray(arr1, arr2, n);
return 0;
}출력
Final array: 9 17 25 8 10
복잡도 분석
정렬 단계에서 O(n log n)의 시간이 소요되며, 이후 해시 맵을 이용한 요소 선택과 배열 순회는 선형 시간 O(n)에 처리됩니다. 따라서 이 알고리즘의 전체 시간 복잡도는 O(n log n)이고, 해시 맵과 복사본 배열 저장을 위해 O(n)의 추가 공간이 필요합니다.