[LeetCode] 1338. Reduce Array Size to The Half

문제 출처: https://leetcode.com/problems/reduce-array-size-to-the-half/

Reduce Array Size to The Half - LeetCode

 

문제

배열 arr이 주어진다. 배열에서 정수 집합을 선택하고, 선택한 정수를 모두 제거한다.

 

배열 정수의 절반 이상이 제거되도록 하는 집합의 최소 크기를 반환하라.

 

예제

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2

Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has size greater than half of the size of the old array.

Input: arr = [1,2,3,4,5,6,7,8,9,10]
Output: 5

 

풀이

Greedy 방식으로 문제 접근

 

절반 이상이 제거되는 최소 집합의 수를 구해야 하기 때문에, 한 번의 선택으로 최대한 많은 수의 값을 제거하는 것이 좋다고 판단하였기에 탐욕적 방식을 채택하였습니다.

 

문제 해결을 위한 각 파트를 순서대로 정리하면,

 

우선, 각 수가 배열에서 몇 번 등장하는지 빈도수를 계산합니다.

var minSetSize = function(arr) {
  // 각 수의 빈도수 계산
  const freq = new Map();
  for (let val of arr) {
      if (!freq.has(val)) { freq.set(val, 0); }
      freq.set(val, freq.get(val) + 1);
  }
}

이후, 빈도수가 가장 많은 값부터 순차적으로 접근하기 위해서 빈도수를 기준으로 내림차순으로 정렬합니다.

var minSetSize = function(arr) {
  // 각 수의 빈도수 계산
  const freq = new Map();
  for (let val of arr) {
      if (!freq.has(val)) { freq.set(val, 0); }
      freq.set(val, freq.get(val) + 1);
  }

  // 빈도 수를 기준으로 내림차순 정렬
  const list = Array.from(freq.entries());
  list.sort((a, b) => b[1] - a[1]);
}

리스트의 맨 앞부터 시작하여 순차적으로 제거하는 것을 가정, 최초 배열의 사이즈에서 빈도수를 빼면서 최초 사이즈의 절반보다 작아지는 위치가 어느 지점인지 탐색 후 반환하는 것을 마지막으로 알고리즘이 끝납니다.

var minSetSize = function(arr) {
  // 각 수의 빈도수 계산
  const freq = new Map();
  for (let val of arr) {
      if (!freq.has(val)) { freq.set(val, 0); }
      freq.set(val, freq.get(val) + 1);
  }

  // 빈도 수를 기준으로 내림차순 정렬
  const list = Array.from(freq.entries());
  list.sort((a, b) => b[1] - a[1]);
	
  // 최초 배열의 사이즈의 절반보다 작아지는 시점 탐색
  let size = arr.length;
  let i = 0;
  while (size > (arr.length / 2)) { 
      size -= list[i][1];
    i += 1; 
  }

  return i;
}

 

Github: 1338.js

opwe37/Algorithm-Study