Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 최대 동일 빈도(Maximum Equal Frequency) 문제

문제 소개

양의 정수로 이루어진 배열 nums가 주어졌을 때, 배열의 접두사(prefix) 중에서 정확히 한 개의 요소를 삭제했을 때 등장한 모든 숫자의 빈도가 서로 같아지는 가장 긴 접두사의 길이를 반환해야 합니다. 단, 요소를 하나 삭제한 후 남은 요소가 없는 경우에도 모든 숫자가 동일한 빈도(0)를 가진 것으로 간주합니다.

예를 들어 입력 배열이 [3, 3, 2, 2, 6, 4, 4, 6]이라면 결과는 7입니다. 인덱스 4에 있는 값 6을 제거하면 [3, 3, 2, 2, 4, 4]가 되는데, 이때 모든 숫자가 정확히 두 번씩 등장하기 때문입니다.

알고리즘 접근 방법

이 문제는 두 개의 맵(map)을 활용해 배열을 한 번만 순회하면서 O(n) 시간 복잡도로 해결할 수 있습니다.

  • cnt: 각 숫자가 지금까지 몇 번 등장했는지 저장합니다.
  • freq: 특정 빈도값을 가지는 서로 다른 숫자가 몇 개인지 저장합니다.

구체적인 풀이 단계는 다음과 같습니다.

  1. maxf := 0, res := 0으로 초기화하고 맵 cnt와 freq를 선언합니다.
  2. i := 0부터 nums의 크기까지 반복하면서 다음을 수행합니다.
    • x := nums[i], cnt[x]를 1 증가시킵니다.
    • f := cnt[x]
    • freq[f]를 1 증가시키고, freq[f - 1]을 1 감소시켜 기존 빈도 그룹에서 제외합니다.
    • maxf := max(maxf, f)
    • 아래 세 조건 중 하나라도 참이면 res := i + 1로 갱신합니다.
      • maxf * freq[maxf] == i : 방금 추가된 숫자(빈도 1) 하나를 제거하면 나머지 모든 숫자의 빈도가 maxf로 일치하는 경우
      • (maxf - 1) * (freq[maxf - 1] + 1) == i : 가장 많이 등장한 숫자에서 하나를 제거하면 모든 숫자의 빈도가 maxf - 1로 일치하는 경우
      • maxf == 1 : 지금까지의 모든 숫자가 한 번씩만 등장한 경우
  3. 반복이 끝나면 res를 반환합니다.

예제 코드

아래 구현 예시를 통해 더 쉽게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxEqualFreq(vector<int>& nums) {
      int maxf = 0, res = 0;
      map<int, int> cnt, freq;
      for (int i = 0; i < nums.size(); i++) {
         int x = nums[i];
         cnt[x]++;
         int f = cnt[x];
         freq[f]++;
         freq[f - 1]--;
         maxf = max(maxf, f);
         if (maxf * freq[maxf] == i || (maxf - 1) * (freq[maxf - 1] + 1) == i || maxf == 1) {
            res = i + 1;
         }
      }
      return res;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,3,2,2,6,4,4,6};
   cout << (ob.maxEqualFreq(v));
}

입력

{3,3,2,2,6,4,4,6}

출력

7