문제 설명
n개의 서로 다른 원소로 이루어진 배열 A가 있다고 가정해 봅시다. 어떤 회사의 현장(onsite) 결승전에 참가할 수 있는 파이널리스트들이 있으며, 이들의 예선 순위가 배열 A에 담겨 있습니다. 우리가 구해야 할 것은 현장 결승 참가 초대를 거절한 참가자의 최소 인원입니다. 현장 결승의 정원은 총 25명이며, 이 중 일부는 초대를 수락하고 일부는 거절했다고 볼 수 있습니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
A = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28]
이 경우 출력은 3이 됩니다. 순위 1번, 13번, 27번 참가자가 초대를 거절했을 것으로 추정되기 때문입니다.
접근 방법
이 문제의 핵심 아이디어는 간단합니다. 초대는 예선 순위가 높은 순서대로 발송되므로, 순위가 mx인 참가자가 초대 대상에 포함되어 있다면 순위 1부터 mx까지의 모든 참가자가 초대를 받았을 것입니다. 그런데 현장 결승 정원은 25명뿐이므로, 최소한 (mx − 25)명은 초대를 거절해야만 합니다.
따라서 배열 A에서 최댓값을 찾은 뒤, 여기서 25를 빼고 0보다 작으면 0을 반환하면 됩니다.
알고리즘 단계
mx := 0 for initialize i := 0, when i < size of A, update (increase i by 1), do: mx := maximum of mx and A[i] return maximum of mx - 25 and 0
C++ 구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int mx = 0;
for (int i = 0; i < A.size(); i++)
mx = max(mx, A[i]);
return max(mx - 25, 0);
}
int main(){
vector<int> A = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
24, 25, 26, 28 };
cout << solve(A) << endl;
}입력
{ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28 }출력
3
동작 원리와 복잡도
위 예제에서 배열의 최댓값은 28입니다. 순위 28번 참가자가 초대받았다면 순위 1번부터 28번까지 모두 초대를 받았을 것이고, 정원이 25명이므로 최소 28 − 25 = 3명이 초대를 거절했어야 합니다. 만약 최댓값이 25 이하라면 모든 초대 대상이 정원 안에 들어갈 수 있으므로 거절자는 0명입니다.
- 시간 복잡도: O(n) — 배열을 한 번만 순회하여 최댓값을 구합니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 상수 공간만 사용합니다.