해시 알고리즘 자바스크립트 (feat. 폰켓몬)

해시 알고리즘

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. 그 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다. 해시 함수는 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 데이터베이스 검색이나 테이블 검색의 속도를 가속할 수 있다.

특징

• 같은 종류의 자료를 묶어서 파악할 수 있다.
• 긴 길이의 데이터를 짧은 길이의 데이터로 변환하는 알고리즘으로 따라서 제3자는 짧은 길이의 데이터로부터 원래의 데이터를 복구할 수 없어야 하며, 동일한 출력을 갖는 서로 다른 데이터를 찾을 수 없어야 한다.

--> 자바스크립트에서는 Object 형태로 사용되겠구만?

사용될 때?

• 중복된 값 확인: 주어진 배열이나 리스트에서 중복된 값이 있는지 확인할 때 해시를 사용할 수 있습니다. 각 값에 대해 해시 맵을 생성하고 이미 나온 값인지 여부를 빠르게 확인할 수 있습니다.

• 빠른 조회 및 삽입: 특정 값에 대한 조회나 삽입 연산을 빠르게 수행해야 할 때 해시 맵을 사용합니다. 이는 특히 검색이나 룩업이 자주 발생하는 경우 유용합니다.

• 집합 연산: 두 집합 간의 교집합, 합집합, 차집합 등의 연산을 수행할 때 해시 맵을 활용할 수 있습니다. 각 집합의 원소를 해시 맵에 저장하고 연산을 수행합니다.

• 빈도수 계산: 어떤 값이나 문자 등의 빈도수를 계산할 때도 해시를 활용할 수 있습니다. 값과 그 값의 빈도수를 해시 맵에 저장하여 효율적으로 계산할 수 있습니다.

• 문자열 비교 최적화: 문자열을 해시로 매핑하여 빠르게 비교하는 경우도 있습니다. 이를 통해 문자열 비교 시간을 최적화할 수 있습니다.

문제가 위의 케이스를 이용하게 된다면, Hash 알고리즘을 사용해서 문제를 접근해보도록 하자.

문제

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

문제 설명

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

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

제한사항

nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

입출력 예

내 풀이

function solution(nums) {
    //서로 다른 종류의 폰켓몬을 가져야 하기 때문에 중복제거를 위해 Set을 사용
  const uniquePokemons = new Set(nums);
    //가져 갈 수 있는 최대 값은 무조건 nums.length/2 입니다. (문제에서 나와 있기 때문)
    //하지만 중복을 제거한 종류 수가 실제 선택한 폰켓몬의 최대 개수 보다 크다면 그 중복된 종류를 제거하고 나머지를 선택할 수 있음.
    //최대한 다양한 종류를 선택하는 것이 목표이기 때문에 작은 값이 결과입니다.
  const maxCount = Math.min(nums.length / 2, uniquePokemons.size);
  return maxCount;
}