C++로 배열에서 지정된 요소를 삭제한 후 최솟값 찾기

문제 개요

이 문제에서는 두 개의 배열 arr[]와 del[]이 주어집니다. 목표는 del[]에 포함된 요소들을 arr[]에서 삭제한 후, 남아 있는 값들 중 가장 작은 값을 찾는 것입니다.

즉, 배열 arr[]의 값 중 del[]에 존재하는 값들을 제거한 뒤, 삭제가 완료된 상태에서의 최솟값을 출력하면 됩니다.

문제를 이해하기 위해 예시를 살펴보겠습니다.

입력

arr[] = {2, 5, 6, 9, 1}
del[] = {1, 5, 9}

출력

2

위 예시에서 del[]에 포함된 1, 5, 9를 arr[]에서 삭제하면 {2, 6}만 남고, 이중 가장 작은 값인 2가 결과가 됩니다.

해결 접근 방법

이 문제의 가장 효율적인 해결 방법은 해싱(hashing)을 활용하는 것입니다. 동작 과정은 다음과 같습니다.

1. del[] 배열의 모든 값을 해시 테이블(unordered_map)에 저장합니다. 이때 값별 개수를 함께 카운트하여 중복 요소 처리에 대비합니다.
2. 배열 arr[]를 순회하면서 각 값이 해시 테이블에 존재하는지 확인합니다.
3. 존재한다면 삭제 대상이므로 건너뛰고(저장된 개수 차감), 존재하지 않는다면 현재까지의 최솟값(minVal)과 비교하여 더 작으면 갱신합니다.
4. 순회가 끝난 후 minVal을 반환합니다.

구현 예시

아래 프로그램은 위 솔루션의 실제 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
int findSmallestVal(int arr[], int m, int del[], int n){
    unordered_map<int, int> delVals;
    for (int i = 0; i < n; ++i) {
        delVals[del[i]]++;
    }
    int minVal = INT_MAX;
    for (int i = 0; i < m; ++i) {
    if (delVals.find(arr[i]) != delVals.end()) {
        delVals[arr[i]]--;
        if (delVals[arr[i]] == 0)
            delVals.erase(arr[i]);
        }
        else
            minVal = min(minVal, arr[i]);
    }
    return minVal;
}
int main(){
    int array[] = { 5, 12, 33, 4, 56, 12, 20 };
    int m = sizeof(array) / sizeof(array[0]);
    int del[] = { 12, 4, 56, 5 };
    int n = sizeof(del) / sizeof(del[0]);
    cout<<"The smallest value after the deleting element is "<<findSmallestVal(array, m, del, n);
    return 0;
}

출력 결과

The smallest value after the deleting element is 12

위 예시에서 del[] = {12, 4, 56, 5}에 해당하는 값들을 삭제하면 {33, 12, 20}이 남습니다. del[]에는 12가 하나만 포함되어 있으므로 arr[]에 있던 두 개의 12 중 하나는 유지되며, 따라서 최종 최솟값은 12가 됩니다.

복잡도 분석

• 시간 복잡도: O(m + n) — arr[]와 del[]를 각각 한 번씩 순회합니다. (m은 arr[]의 크기, n은 del[]의 크기)
• 공간 복잡도: O(n) — del[]의 값을 저장하기 위한 해시 테이블이 추가로 필요합니다.