해시 - 폰켓몬 [코딩테스트 고득점 Kit]

https://school.programmers.co.kr/learn/courses/30/lessons/1845?language=javascript

프로그래머스

 

해시 알고리즘 활용 문제

 

해시 알고리즘을 활용하는 문제는 일반적으로 데이터를 효율적으로 저장하고 검색하기 위해 사용된다.

해시 알고리즘은 주어진 데이터를 해시 함수를 통해 고유한 값으로 매핑하여 저장하므로, 데이터를 빠르게 검색할 수 있다.

 

주어진 문제에서는 각 폰켓몬의 종류 번호를 고유한 값으로 사용하여 폰켓몬의 종류를 식별하는 것이 중요하다.

이런 경우에는 해시 알고리즘을 사용하여 데이터를 효율적으로 관리할 수 있다.

 

일반적으로 해시 알고리즘을 사용하는 문제는 다음과 같은 특징을 가진다.

 

1. 데이터 검색이 빈번한 경우 : 데이터를 빠르게 검색해야 하는 경우 해시 알고리즘이 유용하다. 해시 알고리즘을 사용하면 데이터를 해시 테이블에 저장하고, 이를 통해 빠르게 검색할 수 있다.

 

2. 고유한 식별자가 필요한 경우 : 각 데이터가 고유한 식별자를 가져야 하는 경우 해시 알고리즘이 유용하다. 해시 함수를 통해 고유한 값을 생성할 수 있으며, 이를 통해 각 데이터를 고유하게 식별할 수 있다.

 

3. 중복을 방지해야 하는 경우 : 중복된 데이터를 방지해야 하는 경우 해시 알고리즘이 유용하다.

Set을 사용하면 중복된 값을 허용하지 않는 데이터 구조를 생성할 수 있다.

 

따라서 주어진 문제에서는 각 폰켓몬의 종류를 고유한 값으로 식별해야 하고, 데이터 검색이 필요한 상황이므로 해시 알고리즘을 사용할 수 있다. 이 문제에서는 중복된 값이 없는 Set을 사용하여 각 폰켓몬의 종류를 저장하고, 이를 통해 최대한 다양한 종류의 폰켓몬을 선택하는 방법을 구현할 수 있다.

 

 

문제가 요구하는 것 : Set을 활용하자, 배열에서 중복 제거를 위해
각 폰켓몬의 종류 번호는 숫자로 표현되어 있으므로 Map을 사용할 필요가 없다.

주어진 배열에서 중복되지 않는 폰켓몬의 종류를 최대한 많이 선택하는 것이 목표이다.

주어진 폰켓몬들을 선택할 때, 중복을 허용하지 않는 특성을 이용하여 Set을 사용하자.

 

Set은 중복된 값을 허용하지 않는 데이터 구조이기 때문에, 배열에서 중복된 값들을 제거하고 유일한 값만을 남길 수 있다.

 

그리고 각 폰켓몬의 종류 번호는 각각 숫자로 표현되어 있다. 이러한 특성 때문에 Map을 사용할 필요가 없다. 

Map은 키 - 값 쌍의 모음이며, 주로 킼에 대응되는 값을 검색할 때 사용한다. 이 문제에서는 각 폰켓몬의 종류 번호를 키로 사용하여 특별한 값에 대응시킬 필요가 없기 때문에 Map을 사용할 필요가 없다.

 

주어진 코드에서는 먼저 Set을 사용하여 중복을 제거한 폰켓몬의 종류를 구하고, 이를 통해 선택할 수 있는 최대 종류의 개수를 계산한다.

 

만약, 구한 종류의 개수가 선택 가능한 최대 개수인 N/2 를 초과하면 N/2를 반환하고, 그렇지 않으면 구한 종류의 개수를 반환한다.

 

정답 코드에 대한 주석을 보면 이해가 갈 것이다!

function solution(nums) { // nums는 폰켓몬의 종류가 담긴 1차원 배열
    let answer = 0; // 초기값으로 사용될 변수 answer를 선언
    
    let myBag = [...new Set(nums)]; // 주어진 배열 nums를 Set으로 변환하여 중복을 제거한 새로운 배열 myBag을 생성
    let limit = nums.length / 2; // 폰켓몬을 선택할 때 최대 선택 가능한 개수인 N/2를 구함
    
    return myBag.length > limit ? limit : myBag.length; // 중복을 제거한 폰켓몬의 종류 개수가 최대 선택 가능한 개수를 초과하면 limit을 반환하고, 그렇지 않으면 중복을 제거한 폰켓몬의 종류 개수를 반환
}

 

Set() mdn 문서에서 배열과의 관계성을 확인했다.
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Set#%EB%B0%B0%EC%97%B4%EA%B3%BC%EC%9D%98_%EA%B4%80%EA%B3%84