Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 다른 배열을 활용해 배열 요소 최대화하기

문제 정의

크기가 n인 두 개의 배열이 주어졌을 때, 두 번째 배열의 원소를 활용하여 첫 번째 배열을 최대화해야 합니다. 새로 만들어진 배열은 두 배열 전체에서 가장 큰 n개의 고유한(중복 없는) 원소로 구성되며, 두 번째 배열에 우선순위가 주어지므로 두 번째 배열의 원소들이 첫 번째 배열의 원소보다 앞쪽에 배치되어야 합니다. 또한 결과 배열에서 원소의 등장 순서는 입력 배열에서의 순서와 동일하게 유지되어야 합니다.

예를 들어 arr1[] = {12, 15, 10}이고 arr2[] = {16, 17, 5}라면, 순서를 유지한 채 두 배열에서 선택한 최대 원소들은 {16, 17, 15}가 됩니다.

알고리즘

  1. 크기가 2 × n인 임시 배열을 생성합니다.
  2. arr1과 arr2의 모든 원소를 임시 배열에 저장한 뒤 내림차순으로 정렬합니다.
  3. 입력 배열의 원래 순서를 유지하기 위해 해시 테이블(집합)을 사용합니다.
  4. 정렬된 임시 배열에서 가장 큰 n개의 고유한 원소를 해시 테이블에 저장합니다.
  5. 두 번째 배열(arr2)을 먼저 순회하면서 해시 테이블에 존재하는 원소들을 임시 배열에 차례대로 저장합니다.
  6. 이어서 첫 번째 배열(arr1)을 순회하면서 해시 테이블에 존재하는 나머지 원소들을 저장합니다.
  7. 이 과정을 거치면 두 배열에서 추출한 n개의 고유한 최대 원소들이 우선순위와 순서를 그대로 유지한 채 임시 배열에 담기게 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

void printArray(int *arr, int n){
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

bool compare(int a, int b){
    return a > b;
}

void getMaxElements(int *arr1, int *arr2, int n){
    vector<int> temp(2 * n);
    int k = 0;

    // 두 배열의 원소를 임시 배열에 합침
    for (int i = 0; i < n; ++i) {
        temp[k++] = arr1[i];
    }
    for (int i = 0; i < n; ++i) {
        temp[k++] = arr2[i];
    }

    // 내림차순 정렬
    sort(temp.begin(), temp.end(), compare);

    // 가장 큰 n개의 고유한 원소를 해시 집합에 저장
    unordered_set<int> hash;
    int i = 0;
    while ((int)hash.size() != n) {
        if (hash.find(temp[i]) == hash.end()) {
            hash.insert(temp[i]);
        }
        ++i;
    }

    // 두 번째 배열 우선 처리
    k = 0;
    for (int i = 0; i < n; ++i) {
        if (hash.find(arr2[i]) != hash.end()) {
            temp[k++] = arr2[i];
            hash.erase(arr2[i]);
        }
    }

    // 첫 번째 배열 처리
    for (int i = 0; i < n; ++i) {
        if (hash.find(arr1[i]) != hash.end()) {
            temp[k++] = arr1[i];
            hash.erase(arr1[i]);
        }
    }

    // 결과를 첫 번째 배열에 복사
    for (int i = 0; i < n; ++i) {
        arr1[i] = temp[i];
    }
}

int main(){
    int arr1[] = {12, 15, 10};
    int arr2[] = {16, 17, 5};
    int n = sizeof(arr1) / sizeof(arr1[0]);

    cout << "First array:\n";
    printArray(arr1, n);
    cout << "Second array:\n";
    printArray(arr2, n);

    getMaxElements(arr1, arr2, n);

    cout << "Maximum array:\n";
    printArray(arr1, n);
    return 0;
}

실행 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

First array:
12 15 10
Second array:
16 17 5
Maximum array:
16 17 15

복잡도 분석

시간 복잡도: O(n log n) — 두 배열을 합친 뒤 수행하는 정렬 단계가 전체 성능을 지배합니다.
공간 복잡도: O(n) — 크기 2n의 임시 배열과 최대 n개의 원소를 저장하는 해시 집합이 필요합니다.

핵심 포인트 정리

  • 내림차순 정렬을 통해 가장 큰 값부터 순서대로 검토할 수 있습니다.
  • 해시 집합(unordered_set)을 사용하면 중복 제거와 원소 존재 여부 확인을 평균 O(1)에 처리할 수 있습니다.
  • 두 번째 배열을 먼저 순회함으로써 '두 번째 배열 우선'이라는 조건을 자연스럽게 만족시킵니다.
  • 원본 배열을 다시 한번 순회하므로 입력 배열의 상대적인 순서가 결과에 그대로 보존됩니다.