프로그래머스 | 폰켓몬 (최대한 많은 종류를 선택)

📌 문제

주어진 배열 nums에서 N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 반환하세요.
같은 종류의 폰켓몬은 같은 숫자를 반환합니다.

• 예) 펭도리 -> 1번, 피카츄 -> 2번, 파이리 -> 3번

예를 들어, [3, 1, 2, 3, 3, 2]이 주어졌을 때, 총 6/2 = 3종류를 선택할 수 있으며, [3,1,2]번 중에 고를 수 있습니다. 따라서 이 경우에는 3가 반환되어야 합니다.

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 항상 짝수이며, 1 이상 10,000 이하의 자연수입니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.

✨ 해결 방법

우선 골라갈 수 있는 폰켓몬의 수는 N/2개이므로, nums.length/2라고 표현할 수 있습니다.

function solution(nums) {
  let draw = nums.length / 2;

최대한 다양한 종류를 가져가야 한다는 것은, 최대한 중복을 피해야 한다는 것을 의미합니다. 따라서 set을 통해 중복을 걸러내고, 각 종류마다 몇 개가 있는지 저장합니다.

function solution(nums) {
  let draw = nums.length / 2;
  let option = new Set(nums).size;
}

마지막으로, 최대한 많이 가져갈 수 있는 종류는 몇가지인지 구해야 합니다. 이때의 경우는 두 가지로 나뉩니다.

포켓몬 종류 > 가져갈 수 있는 포켓몬 수 : draw

예를 들어 3개의 종류가 있을 때 총 2개를 가져갈 수 있다면, 아무리 포켓몬 종류가 많아도 가져갈 수 있는 수는 2가지가 최대입니다. 따라서 가져갈 수 있는 수가 최댓값입니다.

포켓몬 종류 < 가져갈 수 있는 포켓몬 수 : type

만약 2개의 종류가 여러 번 중복되어 있을 때 총 3개를 가져갈 수 있다면, 최대한으로 다양하게 가져가도 2개의 종류를 넘어갈 수 없습니다. 따라서 폰켓몬 종류가 최댓값입니다.

💻 solution

function solution(nums) {
  // 골라갈 수 있는 폰켓몬 수
  let draw = nums.length / 2;
  // 겹치지 않는 폰켓몬 번호 조합
  const type = new Set(nums);
  // 겹치지 않는 폰켓몬의 수
  let option = type.size;
  // 폰켓몬 수가 고를 수 있는 수보다 큼 -> 고를 수 있는 수
  // 폰켓몬 수가 고를 수 있는 수보다 작음 -> 겹치지 않는 폰켓몬의 수
  return option > draw ? draw : option;
}

위 식을 이어서 쓰면 이와 같습니다.
하지만, 위의 식은 아래와 같이 더 간략화가 가능합니다.

function solution(nums) {
  return Math.min(new Set(nums).size, nums.length / 2);
}