[프로그래머스] 폰켓몬

폰켓몬

접근 방법

완주하지 못한 선수 문제를 풀어보면서 각 컬렉션들의 시간복잡도와 특징들에 대해 알게 되었다. 그리고 폰켓몬 문제는 최대한 다양한 종류의 폰켓몬을 가지기 원하기 때문에 폰켓몬의 종류 번호는 중복이 되어도 상관 없다고 생각이 들었다.

그렇기 때문에 폰켓몬의 종류가 담긴 1차원 배열을 HashSet컬렌션에 담아서 문제를 접근해보았다.

사용한 자료구조

HashSet

객체들을 순서 없이 저장하고 동일한 객체를 중복 저장하지 않는다.

따라서 문제에서 요구하는 답은 최대한 다양한 종류의 폰켓몬을 n(1차원 배열에 담긴 폰켓몬 수)/2개만큼 선택하고, 선택한 폰켓몬의 종류의 개수를 구해야한다.

하지만 HashSet은 중복 저장하지 않기 때문에 만약 n/2개가 HashSet의 길이보다 더 작다면 n/2를 return하고, 더 크다면 HashSet의 길이를 return 하면 된다.

추가로 설명하면 가장 다양한 종류의 폰켓몬을 n/2개 만큼 담아야 하는데 HashSet길이(중복없는 폰켓몬) < n/2라면 가장 다양하게 담는 방법이 HashSet길이보다 클 수 없기 때문이다.
그리고 HashSet길이(중복없는 폰켓몬) > n/2라면 무슨 일이 있어도 n/2개보다 다양한 폰켓몬을 담을 수 없기 때문이다.

즉, 이번 문제는 어떤 폰켓몬 종류를 담아야하는데 중점을 두는 것이 아니라 종류의 상관없이 폰켓몬 종류의 개수만 return하면 된다.

작성 코드

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int n = nums.length / 2;
        
        Set<Integer> set = new HashSet<>();
        
        for(int i = 0 ; i<nums.length; i++){
            set.add(nums[i]);
        }
        
        if(n < set.size()){
            return n;
        }
        return set.size();
      }
 }