[프로그래머스] 폰켓몬 (Lv. 1, JavaScript)

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

📝 문제 설명

• 목표: 총 N마리의 폰켓몬 중 절반인 N/2마리를 선택할 때, 가질 수 있는 폰켓몬 종류 수의 최댓값을 구하는 문제.
• 핵심 조건:
  • 폰켓몬은 종류에 따라 고유 번호로 구분됨.
  • 최대한 다양한 종류로 골라야 함.
  • 만약 존재하는 종류의 수가 N/2보다 크더라도, 고를 수 있는 최대 마리 수는 N/2로 제한됨.

---

🔍 풀이 과정

문제의 목적은 주어진 nums 배열에서 뽑을 수 있는 폰켓몬의 종류 수 최댓값을 구하는 것이다. N마리 폰켓몬이 주어지면 절반인 2/N 번 뽑을 수 있다. 알아야하는 것은 선택하는 폰켓몬의 종류이기 때문에 주어진 nums에서 폰켓몬의 종류가 몇 가지인지를 알아낼 필요가 있습니다.

만약 [3, 3, 2, 1] 이렇게 주어졌다면 폰켓몬 종류는 [1, 2, 3] 세 가지가 된다. 이 때 선택할 수 있는 폰켓몬의 수는 2마리이므로 최대 2종류를 선택할 수 있습니다.

[3,3,3,2,2,4]으로 주어졌다면 종류는 [2, 3, 4] 세 가지가 된다. 선택할 수 있는 폰켓몬의 수는 3마리 이므로 최대 3 종류의 폰켓몬을 선택할 수 있고,

[3,3,3,2,2,2] 으로 주어졌다면 종류는 [2. 3] 두 가지이다. 이 때 선택할 수 있는 수는 3마리이고 이 때는 두 마리를 선택하고 중복되는 종류의 폰켓몬 한 마리를 선택하는 경우로 최대 두 종류 선택이 가능합니다.

이를 통해 알 수 있는건, 주어진 폰켓몬 배열에서 나오는 종류의 수보다 선택할 수 있는 마리 수가 작다면 선택하는 마리 수만큼이 종류의 최댓값이 되고, 크다면 총 종류 가지수를 따라가게 됩니다.

이를 세 가지 단계에 따라 구현하였다.

1. 선택할 수 있는 폰켓몬 마리 수 계산
   1. nums.length / 2
2. nums 배열에서 종류가 중복되는 폰켓몬은 제거하고 총 종류 수를 파악
   1. 중복을 허용하지 않는 Set 객체를 생성하여 nums 배열의 항목들을 add 한다.
3. 총 종류 수와 선택하는 마리 수를 비교하여 위에서 정리한 대로 반환한다.

4. if (hashMap.size >= pickCount) { 
   answer = pickCount 
   } else { 
   answer = hashMap.size } 
   return answer;

🛠️ 트러블슈팅

잘못된 초기 접근

문제의 목적은 결국 최대한 뽑을 수 있는 폰켓몬의 종류의 수만 알아내는게 목표인데

처음에는 [3, 3, 2, 1] 배열이 주어지면, [[1], [2], [3, 3]] 처럼 종류 별로 해시 테이블을 구성하고, 크기가 작은 버킷부터 우선 추출해며 반복문을 돌리는 복잡한 방식을 구상했었습니다.

그러다가 결국 이렇게 복잡한 순회를 거치면서 종류의 최댓값을 구할 필요가 없다는 사실을 알게 되었습니다. 결국 ‘종류의 수’만 파악하면 되는 문제이기 때문에, 종류가 중복되는 폰켓몬만 걸러내고 주어진 총 종류의 수와 뽑을 수 있는 개수를 비교하면 결과 값이 나오는 매우 단순한 문제였습니다.

---

💻 코드 (Code)

제출한 코드

function solution(nums) {
    let answer = 0;
    const pickCount = nums.length / 2;

    let hashMap = new Set();

    nums.forEach((num) => {
        hashMap.add(num);
    });

    if (hashMap.size >= pickCount) {
        answer = pickCount
    } else {
        answer = hashMap.size
    }


    return answer;
}

최적화된 코드

funcion solution(nums) {
    const pickCount = nums.length / 2;

    // forEach 생략
    const hashMap = new Set(nums);

    // 가져갈 수 있는 수와 종류의 수 중 더 작은 값이 정답
    return Math.min(hashMap.size, pickCount);
}

---

❓ 꼬리 질문 및 복습 (Self-Q&A)

JS의 Set 객체

Set은 중복을 허용하지 않는 데이터 집합으로 new Set(배열) 이런 식으로 배열을 매개변수로 넘겨주면 알아서 배열에서 중복을 걸러낸다. 따라서 초기 Set을 구성할 때 배열을 순회하면서 add 할 필요가 없이 바로 초기화가 가능하다.

해시 테이블 구조이기 때문에 배열에 비해 성능이 좋다.

Set의 경우에는 Set의 크기를 구할때는 length가 아닌 size 프로퍼티를 사용하여 구할 수 있다.

Set 인스턴스의 메서드

• Set.prototype.add(): 같은 값인 요소가 Set에 없다면 삽입
• Set.prototype.clear(): Set의 모든 요소를 삭제
• Set.prototype.delete(): 지정한 요소를 Set에서 제거
• Set.prototype.has(): 특정 값의 존재 여부 확인
  • 시간 복잡도가 O(1)이기 때문에 배열의 includes() 비해 좋은 성능

이 문제에서 알아야할 자료구조나 알고리즘은 무엇이있을까?

해시(Hash). 중복을 식별하고 제거하여 유일한 키(Key)값들의 모음을 다루고 크기를 판별하는 것이 핵심

더 좋은 해결 방법은 없을까?

기존의 if-else 분기문을 Math.min() 내장 함수로 대체하여 코드의 길이를 줄이고 의도를 더 명확하게 표현할 수 있었다.

---

💬 마무리하며

너무 오랜만에 알고리즘 문제를 풀고 최근에 너무 AI에 의존해서일까 기본적으로 알아야할 JS의 내장 객체나 함수에 대해 활용을 제대로 하지 못했던 것 같습니다. 코테 준비를 시작하면서 앞길이 막막하다고 느껴집니다… 그래도 정신차리고 지금이라도 꾸준히 기록 남기면서 발전해나가야 함을 다시 한 번 느끼게 됩니다.