[해시] 프로그래머스 '폰켓몬' - js

1. 문제

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

프로그래머스

2. 설명

해당 문제는 알고리즘 개념 중 '해시'를 사용하여 푸는 문제이다. 해시 테이블은 key-value가 1:1 매핑되어 있기 때문에 검색, 삽입, 삭제 과정에서 모두 평균적으로 O(1)의 시간복잡도를 갖는다.

해시를 사용하여 문제를 풀 때는 Map 또는 Object를 사용하면 된다고하는데, 나는 Map을 선택했다. Map이 좀 더 효율적이라고 하여...ㅎㅎ

먼저 new Map()을 통해 새로운 맵을 만들어준 후, for문을 돌며 key로 폰켓몬의 이름인 nums 배열의 각 요소를(숫자), value로 만약 nums[i] 값이 맵에 있다면 그 값에 +1을 없다면 0에 +1을 하도록 만든다.

만약 맵의 사이즈가 우리가 선택해야하는 폰켓몬의 수가 되는 nums의 길이의 1/2 보다 크다면 선택해야하는 폰켓몬의 선택지가 충분하여 nums의 길이의 1/2를, 작거나 같다면 맵의 사이즈를 리턴한다.

※ 맵의 길이는 .size로 확인할 수 있다!

3. 코드

function solution(nums) {
    const map = new Map();
    
    for(let i=0;i<nums.length;i++){
        map.set(nums[i], (map.get(nums[i]) || 0) + 1);
    }
    
    return map.size > nums.length / 2 ? nums.length / 2 : map.size;
}