이번 문제에서는 N개의 요소로 이루어진 배열이 주어지며, 제거 시간이 대기 시간보다 크거나 같은 경우에만 요소를 제거할 수 있을 때, 제거할 수 있는 요소의 최대 개수를 구하는 것이 목표입니다.
여기서 각 요소의 값은 해당 요소를 배열에서 제거하는 데 걸리는 시간, 즉 제거 시간을 의미합니다.
대기 시간은 해당 요소가 실제로 제거되기까지 기다려야 하는 시간으로, 자신보다 앞서 제거된 모든 요소의 제거 시간을 합산한 값입니다.
즉, 어떤 요소는 제거 시간이 대기해야 하는 시간보다 크거나 같을 때에만 제거할 수 있습니다.
우리는 배열에서 제거할 수 있는 요소의 최대 개수를 찾아야 하며, 필요에 따라 배열 내 요소들의 순서는 자유롭게 변경할 수 있습니다.
예시를 통해 문제를 자세히 이해해 보겠습니다.
입력: arr[] = {12, 3, 11, 7, 5}
출력: 2
예제 풀이
먼저 배열을 오름차순으로 정렬합니다.
정렬된 배열: {3, 5, 7, 11, 12}
이제 요소를 하나씩 제거해 보겠습니다.
- 3 제거 — 대기 시간은 0으로, 제거 시간(3)보다 작으므로 제거가 가능합니다.
- 5 제거 — 대기 시간은 3으로, 제거 시간(5)보다 작으므로 제거가 가능합니다.
- 7 제거 — 대기 시간은 8(3+5)로, 제거 시간(7)보다 크므로 제거가 불가능합니다.
따라서 정답은 2가 됩니다.
이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 배열을 오름차순으로 정렬한 뒤 앞에서부터 차례대로 요소를 검사하며 제거 조건을 확인합니다. 작은 값부터 제거해야 누적되는 대기 시간을 최소화할 수 있어, 결과적으로 더 많은 요소를 제거할 수 있기 때문입니다.
알고리즘
- 배열을 오름차순으로 정렬합니다.
- 배열의 각 요소에 대해 다음을 반복합니다.
- 현재 요소의 대기 시간을 계산합니다(앞선 모든 요소의 제거 시간의 합).
- 대기 시간이 제거 시간 이하이면 해당 요소를 제거하고 제거 횟수(removeCount)를 1 증가시킵니다.
- 조건을 만족하지 않으면 반복을 종료(break)합니다.
- 최종적으로 제거된 요소의 개수를 반환하여 출력합니다.
C++ 구현 예제
아래 프로그램은 제거 시간이 대기 시간 이상일 때 배열에서 제거할 수 있는 최대 요소 개수를 구합니다.
#include <bits/stdc++.h>
using namespace std;
int countRemovedElements(int arr[], int n){
sort(arr, arr + n);
int removeCount = 0;
int waitTime = 0;
for (int i = 0; i < n; i++) {
if (arr[i] >= waitTime) {
removeCount++;
waitTime += arr[i];
}
else
break;
}
return removeCount;
}
int main(){
int arr[] = { 12, 3, 11, 7 , 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"배열에서 제거할 수 있는 최대 요소 개수는 "<<countRemovedElements(arr, n);
return 0;
}실행 결과
배열에서 제거할 수 있는 최대 요소 개수는 2
시간 복잡도
정렬에 O(N log N), 배열 순회 및 제거 검사에 O(N)이 소요되므로 전체 시간 복잡도는 O(N log N)입니다. 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.