1338. Reduce Array Size to The Half

https://leetcode.com/problems/reduce-array-size-to-the-half

불러오는 중입니다...

 

D 풀이

map 을사용하여 같은 요소의 가중치를 준다.

이후 vector 에 가중치값을 삽입하고 오름차순 정렬을 한다.

배열의 사이즈 절반 보다 가중치의 값이 크다면 가장 적은 숫자를 제거하여서 vector 의 크기를 절반으로 줄일수 있다.

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        const int size = arr.size();
        map<int, int> m;

        for (int i = 0; i < size; i++) {
            m[arr[i]]++;
        }

        const int half = size / 2;

        vector<int> vi;
	    for (const auto& s : m)
		    vi.push_back(s.second);

	    sort(vi.begin(), vi.end(), greater<int>());
        
        int sol = 0;
        int sum = 0;
        for (auto a : vi) {
            sol++;
            sum += a;
            if (sum >= half) {
                break;
            }
        }
        return sol;
    }
};

 

O 풀이

int minSetSize(vector<int>& arr) {
      //입력된 숫자 배열 중 사이즈를 반 이하로 내려가도록 숫자를 제거하는 최소 회수를 리턴하라.
      int nArrSize = arr.size();
      int nHalf = nArrSize / 2;
      unordered_map<int, int> oUmap;
      for( int i = 0; i < nArrSize; i++ )
          oUmap[arr[i]]++;

      int nCount = oUmap.size();
      vector<int> oVec;
      oVec.reserve(nCount);
      
      for( unordered_map<int, int>::iterator iter = oUmap.begin();
         iter != oUmap.end(); iter++ )
         oVec.push_back(iter->second);
   
      sort(oVec.begin(), oVec.end(), greater<int>());
      
      int nSum = 0;
      int nLoopCnt = 0;
      for( int i = 0; i < oVec.size(); i++ )
      {
         nLoopCnt++;
         nSum += oVec[i];
         if( nSum >= nHalf )
            break;
      }

      return nLoopCnt;
    }

 

B 풀이

amotized

unoderded hash 를 사용함 충돌이 일어나면은 chaning 하는데, 체이닝이 자주 일어나는 경우 rehash 가 필요해진다.(기준이 보통: 실제 데이터 * 2 < 해쉬맵용량) 

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        map<int, int> my;
        for (int i = 0; i < arr.size(); ++i) {
            my[arr[i]]++;
        }
        map<int,int>::iterator it = my.begin();
        vector<int> cntArr;
        for (; it != my.end(); ++it) {
            cntArr.push_back(it->second);
        }
        sort(cntArr.begin(), cntArr.end(), greater<int>());
        long long sum = 0;
        int idx = 0;
        while (sum < (arr.size() + 1) / 2) {
            sum += cntArr[idx++];
        }
        return idx;
    }
};