[ 프로그래머스 ] 찾아라 프로그래밍 마에스터- 포켓몬 ( java )

[ 프로그래머스 ] 찾아라 프로그래밍 마에스터- 포켓몬 ( 자바 ) 

N마리의 포켓몬에서 N/2 마리를 선택한다. 

포켓몬마다 종류에 따른 번호가 부여되어 있는데, N/2마리르 선택했을 때, 가능한 가장 많은 종류 개수 구하기 

 

 

출처: 프로그래머스 코딩 테스트 연습,  https://programmers.co.kr/learn/courses/30/lessons/1845

코딩테스트 연습 - 폰켓몬 | 프로그래머스

 

핵심 

1. 처음에 완탐으로 (nCn/2) 모든 선택 가능한 가짓수를 구하고 hashSet으로 종류를 세려고 했다. 
   하지만, N은 최대 200,000으로 완탐하면 시간초과된다. 

2. 목적이 가능한 최대한 많은 수를 구해야 한다.
   단순하게 hashSet( 또는, treeSet) 을 이용하여 모든 종류를 구하고 비교하여 답을 계산한다. 구조 참고
   이 문제는 hashSet써도 통과되지만, hash collision 대비해서 treeSet쓰기, O(N) -> O(logN) 

    

 

구조 

for ( 모든 포켓몬에 대해 ) 

    treeSet에 포켓몬 종류 넣기 

 

if ( treeSet.size > N/2 )

    return N/2

else  

    return treeSet.size

 

1 모든 종류가 N/2보다 많다면, N/2 뽑는 것 중 최대는 N/2다. 

2 모든 종류가 N/2보다 적다면, N/2 뽑는 것 중 최대는 전체 종류. 

이렇게 굳이 모든 경우를 구해보지 않아도 된다. 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

코드

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        
        TreeSet<Integer> hs = new TreeSet<Integer>();
        for(int i = 0 ; i < nums.length; i++){
            hs.add(nums[i]);
        }
        if(nums.length/2 < hs.size()){
            return nums.length/2;
        }else{
            return hs.size();
        }
    }
}