Github

폰켓몬

1. 개요

2. 문제 설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

  1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택

  2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택

  3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택

  4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택

  5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택

  6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다. 당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

2-1. 문제 설명 - 제한사항

  • nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.

  • nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.

  • 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.

  • 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

2-2. 문제 설명 - 입출력 예

nums
result

[3,1,2,3]

2

[3,3,3,2,2,4]

3

[3,3,3,2,2,2]

2

2-3. 문제 설명 - 입출력 예 설명

입출력 예 #1 문제의 예시와 같습니다.

입출력 예 #2 6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다. 가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

입출력 예 #3 6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다. 가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

3. 문제 풀이

function solution(nums) {
  // 1) Map(맵) 생성
  const map = new Map();

  // 2) key가 종류 번호, value가 true인 요소를 map에 저장하기
  nums.forEach((item) => {
    map.set(item, true);
  });

  // 3) map의 크기와 nums길이의 절반을 비교하여 값 리턴하기
  return map.size <= nums.length / 2 ? map.size : nums.length / 2;
}

1) Map(맵) 생성

const map = new Map();

폰켓몬의 종류 번호가 담긴 nums배열을 가지고 Map(맵)을 만들어 관리하기 위해 먼저 비어있는 Map(맵)을 만든다.

Map(맵)을 통해 관리하는 이유는 중복되는 폰켓몬을 제거하기 위함이다.

2) key가 종류 번호, value가 true인 요소를 map에 저장하기

nums.forEach((item) => {
  map.set(item, true);
});

폰켓몬의 관리 번호가 요소로 들어있는 nums배열을 Array.forEach()메서드를 사용하여 반복문을 실행하고 있다.

반복문이 실행되면 key가 폰켓몬의 관리 번호, value가 true인 요소를 Map.set()메서드를 통해 map에 저장한다. 만약 같은 key가 중복된다면 마지막 값이 적용된다. 해당 과정을 통해 중복되는 관리 번호가 있더라도 하나의 요소만 map에 저장된다.

3) map의 크기와 nums길이의 절반을 비교하여 값 리턴하기

return map.size <= nums.length / 2 ? map.size : nums.length / 2;

해당 문제에서 원하는 답은 선택할 수 있는 가장 많은 종류의 폰켓몬의 수이다.

가장 많은 종류의 폰켓몬이 아니라 가장 많이 선택할 수 있는 폰켓몬 이라면 모든 답은 아래와 같을 것이다. 참고로 nums의 짝수라고 제한사항에 명시되어 있다.

return nums / 2;

하지만 우리가 원하는 것은 가장 많은 종류의 폰켓몬의 수이므로 뽑힌 폰켓몬에서 중복되는 번호는 하나로 생각해야 한다.

하나의 예시를 든다. 함께 생각해야 할 조건은 중복이 얼만큼 되어 있던 간에 가장 많은 종류의 폰켓몬의 수의 최대값은 num / 2이다.

  • nums에 100개의 요소가 있고 그 중 중복된 요소를 하나의 요소로 바꾸면 총 80개의 요소가 있다고 하자

    • nums/2: 50

    • map.size: 80

    • 가장 많은 종류의 폰켓몬의 수는 50이다.

  • nums에 100개의 요소가 있고 그 중 중복된 요소를 하나의 요소로 바꾸면 총 40개의 요소가 있다고 하자.

    • nums/2: 50

    • map.size: 40

    • 가장 많은 종류의 폰켓몬의 수는 40이다.

위의 예시에서 살펴본 것을 바탕으로 map.size가 num / 2보다 같거나 작을 경우엔 map.size를 반환하고 그렇지 않을 경우엔 num / 2을 반환한다.

결과

programmers_ponketmon_result

4. 다른 사람의 풀이

가장 좋아요를 받은 풀이를 가져왔다.

function solution(nums) {
  // 1) nums 배열 길이의 절반
  const max = nums.length / 2;

  // 2) Set(셋)을 통한 중복된 번호 제거
  const arr = [...new Set(nums)];

  // 3) arr.length와 max의 값을 비교하기
  return arr.length > max ? max : arr.length;
}

나는 Map(맵)을 사용하여 문제를 풀었지만 위의 풀이에서는 Set(셋)을 사용하여 문제를 풀었다. 사실 내가 푼 풀이에서 중복되는 키만 제거하면 되었지 값은 그다지 필요하지 않았다. 그렇기 때문에 Set(셋)으로 문제를 푸는 것이 문제에 알맞는 풀이라고 생각한다.

1) nums 배열 길이의 절반

const max = nums.length / 2;

폰켓몬의 관리 번호가 중복이 없다는 가정하에 가장 많이 뽑을 수 있는 종류의 폰켓몬 수는 nums / 2이다. 대신 아래의 과정을 통해 중복이 있는 관리 번호를 확인해야 한다.

2) Set(셋)을 통한 중복된 번호 제거

const arr = [...new Set(nums)];

Set(셋)객체는 중복되지 않는 유일한 값들의 집합이다. 그렇기 때문에 동일한 값을 중복하여 포함할 수 없다. 위의 과정에서 nums배열을 넣어 Set(셋)객체가 만들어 지는데 nums배열에 중복된 값은 하나만 저장이 된다.

그 후 스프레드 연산자를 통해 배열로 만들고 이를 arr 변수에 할당하였다.

3) arr.length와 max의 값을 비교하기

return arr.length > max ? max : arr.length;

만약 arr배열의 길이가 max의 크기 보다 크다면 max값이 그렇지 않으면 arr배열의 길이가 반환된다.

2)의 과정을 아래와 같이 바꾼다면?

2) Set(셋)을 통한 중복된 번호 제거는 Set(셋)객체를 만들고 다시 이를 가지고 배열을 만들었다. 하지만 단지 길이를 가져오는 것이기 때문에 2), 3)과정을 아래와 같이 바꾸었다.

const set = new Set(nums);
return set.size > max ? max : set.size;

결과

programmers_ponketmon_result2

5. Conclusion

며칠 전에 배운 Map(맵)을 활용하여 문제를 풀었고 해당 문제는 다른 문제에 비해 빠르게 풀었다. 물론 문제가 쉬웠던 것도 있지만 학습한 내용을 잘 적용하여 풀었다는 것이 뿌듯했다. Set(셋)이라는 개념을 내일 당장 공부해야겠다! 확실히 Map(맵)으로 풀었을 땐 굳이 필요없는 과정이 있었지만 Set(셋)으로 푸니 깔끔하게 풀이가 완성되었다. 코딩 테스트에서 생각보다 Map과 Set를 이용하여 문제를 푸는 경우가 있는 것 같으니 기본기를 잘 다져놔야겠다.

참고

[JavaScript] 37. Set 과 Map

📅 2022-08-11

Previous신규 아이디 추천Next두 개 뽑아서 더하기

Last updated