C++ 배열에서 지정된 요소를 삭제한 후 최댓값 구하기

이 문제에서는 크기가 n인 배열 arr[]와 크기가 m인 또 다른 배열 del[]이 주어집니다. 우리의 과제는 del[]에 포함된 요소들을 arr[]에서 삭제한 뒤, 남아 있는 요소 중 가장 큰 값을 찾는 것입니다. 단, 삭제해야 할 요소가 배열에 여러 번 등장하는 경우에는 첫 번째로 등장하는 인스턴스만 삭제합니다.

문제 이해를 위한 예시

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

설명 −

요소 삭제 후 배열 arr[] : {5, 7, 2}
배열의 최댓값은 7

해결 접근 방법 1 : 삭제 후 정렬

가장 간단한 방법은 arr[]의 요소 중 del[]에 존재하는 요소를 찾아 삭제 처리하는 것입니다. 여기서는 실제로 요소를 제거하는 대신 해당 위치의 값을 INT_MAX로 바꿔 무효화한 후, 배열을 오름차순으로 정렬합니다. 그러면 삭제된 요소(INT_MAX)들은 배열의 맨 뒤로 밀려나므로, 인덱스 (n - m - 1)에 있는 값이 곧 삭제 후 남은 요소들의 최댓값이 됩니다.

이 방법의 시간 복잡도는 삭제 확인에 O(n × m), 정렬에 O(n log n)이 소요됩니다.

예제 코드

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

int findMaxAfterDeletion(int arr[], int n, int del[], int m){
   // del[]의 각 요소와 일치하는 첫 번째 값을 무효화
   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);
   return arr[n - m - 1];
}

int main(){
   int arr[] = { 3, 5, 1, 7, 9, 2 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int del[] = { 1, 9, 3 };
   int m = sizeof(del) / sizeof(del[0]);
   cout << "요소 삭제 후 최댓값은 " << findMaxAfterDeletion(arr, n, del, m);
   return 0;
}

실행 결과

요소 삭제 후 최댓값은 7

해결 접근 방법 2 : 해시 맵 활용

더 효율적인 방법은 해시 맵(unordered_map)을 사용하여 삭제 여부를 빠르게 확인하는 것입니다. 먼저 del[] 배열의 모든 요소와 그 개수를 해시 맵에 저장합니다. 이후 arr[]를 순회하면서 각 요소가 해시 맵에 존재하는지 검사하고, 존재한다면 해당 요소의 개수를 하나 줄여 삭제를 처리합니다(개수가 0이 되면 맵에서 제거). 존재하지 않는다면 현재까지의 최댓값 maxVal과 비교하여 더 큰 값을 저장합니다.

배열 전체의 순회가 끝나면 maxVal에 삭제 후 남은 요소들의 최댓값이 저장되어 있습니다. 이 방법은 해시 맵의 조회가 평균 O(1)이므로 전체 시간 복잡도가 O(n + m)으로, 정렬 기반 방법보다 효율적입니다.

예제 코드

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

int findMaxAfterDeletion(int arr[], int n, int del[], int m){
   unordered_map<int, int> delMap;
   // 삭제할 요소들을 해시 맵에 저장
   for (int i = 0; i < m; ++i) {
      delMap[del[i]]++;
   }
   int maxVal = INT_MIN;
   for (int i = 0; i < n; ++i) {
      if (delMap.find(arr[i]) != delMap.end()) {
         // 삭제 대상이면 개수를 감소시켜 삭제 처리
         delMap[arr[i]]--;
         if (delMap[arr[i]] == 0)
            delMap.erase(arr[i]);
      }
      else
         maxVal = max(maxVal, arr[i]);
   }
   return maxVal;
}

int main(){
   int arr[] = { 3, 5, 1, 7, 9, 2 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int del[] = { 1, 9, 3 };
   int m = sizeof(del) / sizeof(del[0]);
   cout << "요소 삭제 후 최댓값은 " << findMaxAfterDeletion(arr, n, del, m);
   return 0;
}

실행 결과

요소 삭제 후 최댓값은 7

마무리

두 방법 모두 동일한 결과를 출력하지만, 배열의 크기가 커질수록 해시 맵을 활용하는 두 번째 방법이 O(n + m)의 선형 시간 복잡도를 가지므로 훨씬 유리합니다. 반면 첫 번째 방법은 코드가 단순하여 작은 규모의 입력이나 구현 편의성이 중요한 상황에 적합합니다.