[프로그래머스] 포켓몬

🙋 Hash 사용!

왜 Hash일까?

• 중복을 허용하지 않는 자료구조이기때문!

이 문제가 해시로 분류되는것은 알고있었지만, HashMap을 쓴 후 어떻게할까를 고민했다..
우선 중복을 허용하지 않는 키에 포켓몬 번호를 넣고, 조합 알고리즘을 사용해 경우의수를 보면서 종류의 최댓값을 갱신하려고했다.
근데 그럼 번호에 따른 마리수를 값으로 저장하고.. 조합할 때 마다 해당 번호의 마리수가 남아있는지 체크하고.. 로직이 참 복잡하고 코드가 더러워졌다.

그래서 다른 블로그를 보고 힌트를 받았다!

내가 처음에 생각한 로직에서 꼬이기 시작했던건, 조합 알고리즘을 사용하려해서이다.

어떻게 간단하게 풀 수 있을까?

2/n 마리를 가지는거니까, 중복이 없도록 해시에 저장했을 때 해시 사이즈가 2/n 이상이면 2/n을 리턴하면되고, 2/n미만이면 해시 사이즈를 리턴하면된다.

제출 코드

HashMap 사용

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int N = nums.length;
        Map<Integer, Integer> hash = new HashMap<>();
        
        for(int i=0; i<N; i++) {
            hash.put(nums[i], i);
        }
        
        if(hash.size()>= N/2) answer = N/2;
        else answer = hash.size();
        
        return answer;
    }
}

다른 풀이

HashSet 사용

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
		int n = nums.length/2;

		HashSet<Integer> hashSet = new HashSet<Integer>();
		for(int i=0; i<nums.length; i++) {
			hashSet.add(nums[i]);
		}
		if(n < hashSet.size()) answer = n;
		else answer = hashSet.size();
		return answer;
    }
}