C++로 주어진 요소를 삭제한 후 가장 큰 k개의 숫자 찾는 방법

이 문제에서는 크기가 n인 배열 arr[], 크기가 m인 배열 del[], 그리고 정수 k가 주어집니다. 우리의 과제는 주어진 요소들을 삭제한 후 가장 큰 k개의 숫자를 찾는 것입니다.

즉, del[] 배열에 포함된 모든 요소를 arr[]에서 제거한 뒤, 남은 요소 중 가장 큰 k개의 요소를 출력해야 합니다. 만약 동일한 값이 여러 개 존재한다면 첫 번째 인스턴스만 삭제합니다.

예시를 통해 문제를 이해해 보겠습니다.

입력 : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2
출력 : 7, 5

설명 −

요소 삭제 후의 arr[] 배열 : {5, 7, 2}
가장 큰 2개의 요소는 7, 5입니다.

해결 방법 1: 정렬 활용

가장 간단한 해결 방법은 arr[]에서 del[]에 포함된 모든 요소를 삭제하는 것입니다. 그런 다음 배열을 내림차순으로 정렬하고, 앞에서부터 k개의 요소를 출력하면 됩니다.

예제 코드

아래 프로그램은 위 해결 방법의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
void findKmaxElementDelArray(int arr[], int n, int del[], int m, int k){
   for(int i = 0; i < m; i++){
      for(int j = 0; j < n; j++){
         if(arr[j] == del[i]){
            arr[j] = INT_MIN;
            break;
         }
     }
   }
   sort(arr, arr + n, greater<int>());
   for (int i = 0; i < k; ++i) {
      cout<<arr[i]<<" ";
   }
}
int main(){
   int array[] = { 3, 5, 1, 7, 9, 2 };
   int m = sizeof(array) / sizeof(array[0]);
   int del[] = { 1, 9, 3 };
   int n = sizeof(del) / sizeof(del[0]);
   int k = 2;
   cout<<k<<" largest numbers after deleting the elements are ";
   findKmaxElementDelArray(array, m, del, n, k);
   return 0;
}

출력 결과

2 largest numbers after deleting the elements are 7 5

해결 방법 2: 해시맵과 힙(Heap) 활용

또 다른 접근 방식은 해시맵과 최대 힙(max-heap)을 사용하는 것입니다. 먼저 해시맵에 del[] 배열의 모든 요소를 저장합니다. 그다음 arr[] 배열의 요소 중 해시맵에 존재하지 않는 요소들만 최대 힙에 삽입합니다. 마지막으로 힙에서 k개의 요소를 꺼내어 출력합니다.

이 방법은 삭제할 요소를 찾기 위해 매번 배열 전체를 탐색하지 않아도 되므로, 해시맵 조회 연산 O(1) 덕분에 전체적으로 더 효율적인 성능을 기대할 수 있습니다.

예제 코드

아래 프로그램은 위 해결 방법의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
void findKmaxElementDelArray(int arr[], int n, int del[], int m, int k){
   unordered_map<int, int> deleteElement;
   for (int i = 0; i < m; ++i) {
      deleteElement[del[i]]++;
   }
   priority_queue<int> maxHeap;
   for (int i = 0; i < n; ++i) {
      if (deleteElement.find(arr[i]) != deleteElement.end()) {
         deleteElement[arr[i]]--;
         if (deleteElement[arr[i]] == 0) deleteElement.erase(arr[i]);
      }
      else
         maxHeap.push(arr[i]);
   }
   for (int i = 0; i < k; ++i) {
      cout<<maxHeap.top()<<" ";
      maxHeap.pop();
   }
}
int main(){
   int array[] = { 3, 5, 1, 7, 9, 2 };
   int m = sizeof(array) / sizeof(array[0]);
   int del[] = { 1, 9, 3 };
   int n = sizeof(del) / sizeof(del[0]);
   int k = 2;
   cout<<k<<" largest numbers after deleting the elements are ";
   findKmaxElementDelArray(array, m, del, n, k);
   return 0;
}

출력 결과

2 largest numbers after deleting the elements are 7 5