[프로그래머스, 1845번] 폰켓몬 (해시, Hash, Java)

문제설명

입력 & 출력

나의 풀이

이번 "프로그래머스 - 폰켓몬" 문제는 폰켓몬이 배열로 주어졌을 때 최대한 다른 종류의 폰켓몬을 가져갈 수 있는지에대한 문제입니다.

 

Hash문제로, HashSet과 HashMap 두 개다 사용할 수 있습니다.

HashSet 풀이

 

폰켓몬은 최대한 다양한 종류를 선택해야 하기 때문에, 중복을 제거할 수 있는 Set 자료구조를 활용할 수 있습니다.

[JAVA] HashSet 클래스 사용법 (중복 없는 데이터 집합)

 

문제에서 가져갈 수 있는 폰켓몬의 최대 수를 N/2로 제한하고 있으므로, 이 값을 maximum 변수에 저장합니다. 그다음, Set의 add() 메서드를 사용하여 배열 nums의 폰켓몬들을 추가하며 중복을 제거합니다.

 

이후, 최대로 선택할 수 있는 폰켓몬 수(maximum)가 중복 제거된 폰켓몬의 수(set.size())보다 크다면, 선택 가능한 폰켓몬의 수는 set.size()가 됩니다. 반대로, set.size()가 더 크거나 같다면 maximum을 반환하여 해결합니다.

 

HashMap 풀이

 

HashMap을 사용하여 해결하는 방식은 HashSet을 사용하는 방식과 핵심적인 아이디어가 동일합니다.

 

즉, 폰켓몬의 중복을 제거하고, 가능한 최대 종류 수를 구하는 것입니다. 우선, HashMap의 put() 메서드를 사용하여 배열의 각 폰켓몬을 맵에 추가합니다.

 

이때, getOrDefault() 메서드를 사용하여 해당 폰켓몬이 이미 맵에 존재하는 경우 값을 1 증가시키고, 없으면 0에서 시작해 추가합니다. 마지막으로, Math.min 메서드를 사용하여 최대로 선택 가능한 폰켓몬의 수(nums.length / 2)와 중복 제거된 폰켓몬 종류 수(map.size()) 중 작은 값을 반환합니다.

 

이렇게 Math.min을 사용하는 이유는 문제의 조건에 따라, 실제 폰켓몬 종류 수보다 더 많이 선택할 수 없기 때문입니다.

즉, 고유한 종류 수보다 N/2가 작으면 선택 가능한 종류는 N/2로 제한됩니다.