[알고리즘] 프로그래머스 폰켓몬 Java

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 result
[3,1,2,3] 2
[3,3,3,2,2,4] 3
[3,3,3,2,2,2] 2

Code

import java.util.HashSet;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;

        int getNum = nums.length/2;
        HashSet<Integer> set = new HashSet<Integer>();

        for(int i = 0; i <nums.length; i++){
            set.add(nums[i]);
        }

        if(set.size() >= getNum){
            answer = getNum;
        } else{
            answer = set.size();
        }

        return answer;

        // N/2 마리   ex) 6마리 들어오면 그 중 3개를 뽑는데 가질 수 있는 최대 종류 수, 즉, 종류 최댓값
        // 중복 제거
        // 그 최댓값 return
        // 배열을 HashSet으로 변환시키면 중복 제거 됨
        // 1,2,5,5,5,5 -> 1,2,5 || 1,2,2,2,2,2 -> 1, 2
        // Hashset.size() >= getNum ? getNum : Hashset.size()

    }
}

Point

1. 총 N마리가 들어오는데 N/2 만큼 포켓몬을 뽑는다.
2. 단, 포켓몬의 종류는 중복이 가능하다.
3. 그 중 최대한 다양한 종류를 뽑는 경우의 최댓값을 반환.

문제는 위와 같이 해석하였고, HashSet을 사용하여 배열의 중복을 제거하였다.
그리고 HashSet의 길이가 기존 Array의 길이보다 크거나 같다면 배열의 길이의 절반만큼의 종류 최댓값을 갖게되고,
HashSet의 사이즈가 getNum보다 작다면 Hashset.size()만큼의 종류 최댓값을 갖게된다.