정렬된 배열 A가 주어졌을 때, 배열 전체 크기의 25%보다 많이 등장하는 요소를 찾아 반환하는 문제입니다. 예를 들어, A = [1, 2, 4, 4, 4, 4, 5, 5, 6, 6, 7, 7]인 경우 배열의 크기는 12이고, 4는 네 번 등장하므로 전체의 25%를 초과합니다. 따라서 정답은 4가 됩니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 배열을 순회하면서 각 요소의 등장 빈도(빈도수)를 기록합니다.
- 특정 요소의 빈도수가 배열 크기의 25%보다 크면 해당 요소를 결과로 반환합니다.
여기서 핵심은 25% 기준값을 계산하는 것입니다. 배열 크기를 n이라 할 때, n / 4보다 많이 등장하는 요소가 바로 찾고자 하는 특별한 요소입니다. 해시 맵(unordered_map)을 사용하면 각 요소의 빈도를 효율적으로 추적할 수 있으며, 시간 복잡도는 O(n)입니다.
예제 코드
아래는 C++로 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findSpecialInteger(vector<int>& arr) {
int n = arr.size();
int req = n / 4;
unordered_map <int, int> m;
int ans = -1;
for(int i = 0; i < n; i++){
m[arr[i]]++;
if(m[arr[i]] > req)ans = arr[i];
}
return ans;
}
};
main(){
Solution ob;
vector<int> c = {1,2,4,4,4,4,5,5,6,6,7,7};
cout << ob.findSpecialInteger(c);
}
입력
[1,2,4,4,4,4,5,5,6,6,7,7]
출력
4