[Algoritm/Java][프로그래머스] 폰켓몬

[프로그래머스] 폰켓몬

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

문제 설명

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

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(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 하면 됩니다.

Code

import java.util.HashMap;
class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        HashMap<Integer,Integer> ponketmon = new HashMap();
        for(int num: nums){
            ponketmon.put(num,ponketmon.getOrDefault(num,0)+1);
        }

        if(ponketmon.size() > nums.length/2){
            answer = nums.length/2;
        }
        else {
            answer = ponketmon.size();
        }
        return answer;
    }
}

Code 설명

이 문제는 처음 봤을때는 조합을 하나하나 다 세야되는거 같지만 생각해보면 중복되는 것들을 제거한 갯수가
nums.length/2보다 크면 nums.length/2가 answer이고, 그렇지 않다면 중복되는 것들을 제거한 갯수가 answer가 된다.
중복을 제거하기 위해서 저번에 완주하지 못한 선수에서 사용했던 HashMap을 이용하면 중복을 제거할 수 있을것 같아서 사용해 주었다.

배운점

저번에 사용했던 HashMap을 이용해서 문제를 해결하고 나서 다른사람의 풀이를 보니 HashSet이라는 자료구조를 알게되었다.
HashMap은 key와 value가 있지만 HashSet은 value가 있다는 차이점이있다. 주된 차이점은 HashMap이 Map Interface Hierarchy에 속하고 HashSet이 Collection Interface Hierarchy에 속해있는 동안 Collection 인터페이스와 관련이 없다는 것이다 라는건데 무슨 소리인지 잘 모르겠다...
아무튼 이번 문제는 Key가 필요없으므로 HashSet을 이용해서 코드를 바꿔보았다. HashMap을 HashSet으로 바꾸기만 하면 되는 똑같은 구조의 코드이다

HashMap 시간

HashSet 시간

의미있는 시간 차이인지는 모르겠지만 HashSet이 더 빠르긴 하다.

HashSet을 이용한 Code

import java.util.HashSet;
class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        HashSet<Integer> ponketmon = new HashSet();
        for(int num: nums){
            ponketmon.add(num);
        }

        if(ponketmon.size() > nums.length/2){
            answer = nums.length/2;
        }
        else {
            answer = ponketmon.size();
        }
        return answer;
    }
}