[프로그래머스] 폰켄몬

N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

 

처음에 그냥 풀었을 때

public int solution_1_1(int[] nums){
    int answer = 0;
    int half = (int)nums.length/2;

    Arrays.sort(nums);

    int type = 0;
    int prenum = 0;
    for(int i=0; i < nums.length; i++){
        if(prenum != nums[i]){
            type++;
        }
        prenum = nums[i];
    }

    if(half < type) {
        answer = half;
    }else{
        answer = type;
    }
    return answer;
}

1. 먼저 N/2 값을 구한다.

2. 폰켄몬 종류를 구하기 위해 정렬한다.(2313 -> 1233)

3. for 문을 돌려 현재 종류가 이전 값과 다르면 종류 값 ++, 같으면 그냥 넘어간다.

4. N/2 와 종류의 크기 중 더 작은 것을 반환한다.(N이 아무리 커도 종류가 적으면 그 종류만큼만 선택할 수 있으니까)

 

해시맵을 이용해서 푸는 방법

해시맵은 value 값 중복을 허용하지 않는다.

public int solution_1_2(int[] nums){
    int answer = 0;
    HashMap<Integer, Integer> map = new HashMap();

    int half = (int)nums.length/2;

    for(int i=0; i < nums.length; i++){
        map.put(nums[i], nums[i]);
    }
    int type = map.size();

    if(type < half){
        answer = type;
    }else{
        answer = half;
    }

1. 먼저 N/2 값을 구한다.

2. for문을 돌려 그냥 종류 배열을 맵에 넣는다.(중복을 허용하지 않아 같은 종류면 자동으로 덮어쓰기 됨)

3. 똑같이 N/2와 종류 값을 비교해 더 적은 것을 반환한다.

 

해시셋을 이용하는 방법(다른 사람의 풀이)

public int solution_1_3(int[] nums){
    //중복을 제거해주는 해시셋을 생성한다.
    HashSet<Integer> hs = new HashSet<>();
    //자동으로 중복이 제거되므로 종류가 나온다.
    for(int i=0; i < nums.length; i++){
        hs.add(nums[i]);
    }
    //종류와 N/2 중 작은 것을 돌려준다.
    if(hs.size() > nums.length/2){
        return nums.length/2;
    }

    return hs.size();
}

맵과 동일하게 보면 될 것 같다. 이게 더 편하다.

굳이 해시맵에서 <Integer, Integer> 설정할 필요없이 셋으로 객체는 어차피 다르고 value 비교는 알아서 해주니 value 중복 없이 종류를 구할 수 있다.