이 문제에서는 크기 n의 배열 arr[], 크기 m의 배열 del[], 그리고 정수 k가 주어집니다. 우리의 과제는 주어진 요소들을 삭제한 후 가장 작은 k개의 숫자를 찾는 것입니다.
즉, arr[] 배열에서 del[] 배열에 포함된 모든 요소를 삭제한 뒤, 남은 요소들 중 가장 작은 k개의 값을 출력해야 합니다. 만약 동일한 값이 배열에 여러 개 존재한다면, 먼저 등장하는 인스턴스를 삭제합니다.
문제 이해를 위한 예시
입력 : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2
출력 : 2, 5설명 −
요소 삭제 후 arr[] : {5, 7, 2}
가장 작은 2개의 요소는 2, 5입니다.해결 방법 1: 정렬 활용하기
가장 간단한 해결 방법은 del[]에 있는 모든 요소를 arr[]에서 제거하는 것입니다. 이후 배열을 오름차순으로 정렬하고, 정렬된 배열의 처음 k개 요소를 출력하면 됩니다.
이 방법의 시간 복잡도는 삭제 과정에서 O(n×m), 정렬 과정에서 O(n log n)이 소요되므로 전체적으로 O(n×m + n log n)입니다.
구현 예제
아래 프로그램은 위 해결 방법의 동작을 보여줍니다.
#include <bits/stdc++.h>
using namespace std;
void findKminElementDelArray(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_MAX;
break;
}
}
}
sort(arr, arr + n);
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<<"개의 가장 작은 숫자는 ";
findKminElementDelArray(array, m, del, n, k);
return 0;
}실행 결과
2개의 가장 작은 숫자는 2 5
해결 방법 2: 해시맵과 최소 힙 활용하기
또 다른 접근 방식은 해시맵(hashmap)과 최소 힙(min-heap)을 함께 사용하는 것입니다. 동작 과정은 다음과 같습니다.
- 해시맵에
del[]배열의 모든 요소를 저장합니다. arr[]의 요소를 순회하면서 해시맵에 존재하지 않는 요소만 최소 힙에 삽입합니다.- 해시맵에 존재하는 요소라면 해당 카운트를 감소시키고, 카운트가 0이 되면 맵에서 제거하여 중복 삭제 처리를 합니다.
- 마지막으로 힙에서 k개의 요소를 꺼내어 출력합니다.
이 방법은 평균적으로 O(n + m)의 시간 복잡도로 동작하므로, 배열과 삭제 목록의 크기가 클 때 정렬 기반 방법보다 효율적입니다.
구현 예제
아래 프로그램은 위 해결 방법의 동작을 보여줍니다.
#include <bits/stdc++.h>
using namespace std;
void findKminElementDelArray(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, vector<int>, greater<int> > minHeap;
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
minHeap.push(arr[i]);
}
for (int i = 0; i < k; ++i) {
cout<<minHeap.top()<<" ";
minHeap.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<<"개의 가장 작은 숫자는 ";
findKminElementDelArray(array, m, del, n, k);
return 0;
}실행 결과
2개의 가장 작은 숫자는 2 5
마무리
두 가지 접근 방식 모두 올바른 결과를 도출하지만, 입력 크기가 커질수록 해시맵과 최소 힙을 활용하는 두 번째 방법이 더 나은 성능을 보여줍니다. 따라서 실무 환경에서는 데이터 크기와 요구 사항에 따라 적절한 방법을 선택하는 것이 좋습니다.