문제 출처

코딩테스트 연습 > 해시 > 폰켓몬
https://school.programmers.co.kr/learn/courses/30/lessons/1845

문제 설명

폰켓몬의 종류(번호)가 담긴 배열 nums가 주어진다. 이 중 nums.length/2 만큼 가져갈 수 있다. 최대한 많은 종류의 폰켓몬을 포함하여 가져갈 때, 폰켓몬의 종류는 최대 몇 마리인가?

접근 방법

배열 nums 를 HashMap화 시킨다.(key -> 폰켓몬 종류, value -> 갯수)
이 때, '종류'는 map의 크기가 된다. 만약 map의 크기가 배열 nums.length/2 보다 크거나 같다면 num.length/2를 return 아니면 map의 크기를 return 한다.

import java.util.HashMap;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        
        for(int i = 0; i<nums.length; i++){
            Integer k=map.get(nums[i]);
            if(k == null){
                map.put(nums[i],1);
            }else{
                map.replace(nums[i], k+1);
            }
        }
        
        answer = map.size();
        
        if(answer >=nums.length/2){
            return nums.length/2;
        }else{
            return answer;
        }
        
    }
}

Review
문제에서 중점이 되는 것은 '종류'이므로 HashSet을 이용하여 접근할 수 있다.

import java.util.HashSet;

class Solution {
    public int solution(int[] nums) {
        
        HashSet hs = new HashSet<>();
        for(int n : nums){
            hs.add(n);
        }
        
        if(hs.size() >= nums.length/2) return nums.length/2;
        else return hs.size();
    }
}

알게된 점

HashMap의 여러 기능을 사용해 볼 수 있었다.
또한, 문제에서 필요한 것은 각각 key 마다의 value가 필요한 것이 아니라 key의 갯수가 필요하다. 즉, HashSet으로도 풀이가 가능하다.

문제푼 흔적