[프로그래머스] 폰켓몬 (Java)

프로그래머스 폰켓몬

문제풀이

자리, 선택, 종류, 중복 같은 개념들이 등장하면서 이건 조합으로 푸는 문제가 아닐까라고 착각하게 되지만 최악의 경우 2만개 중 1만개를 뽑아야하기에 불가능하다. 조금만 생각해보면 굉장히 간단하게 모든 경우가 다음과 같이 나뉨을 알 수 있다.

• 내가 가질 수 있는 폰켓몬 수(N / 2) > 전체 폰켓몬 종류의 수
  • 전체 폰켓몬 종류의 수 만큼의 폰켓몬 종류를 가질 수 있다.
• 내가 가질 수 있는 폰켓몬 수(N / 2) < 전체 폰켓몬 종류의 수
  • 내가 가질 수 있는 폰켓몬 수 만큼의 폰켓몬 종류를 가질 수 있다.

구현코드

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int totalMonster = nums.length;
        int myMonster = totalMonster / 2;
        int typeCnt = 0;
        int answer = 0;
        
        for(int i = 0 ; i < nums.length ; ++i){
            set.add(nums[i]);
        }
        
        typeCnt = set.size();
        
        answer = typeCnt >= myMonster ? myMonster : typeCnt;
        
        return answer;
    }
}