[Programmers] 폰켓몬 - Java

문제

프로그래머스

 

풀이

포켓몬은 번호로 종류를 구분하는데, N개에서 N/2개를 가져갔을 때, 최대 종류의 개수를 구하는 문제이다.

 

기존풀이

종류가 적은 포켓몬을 먼저 가는 것이 최대 종류의 개수를 가져갈 수 있을 것이라고 생각했다.

 

1. HashMap을 이용해서, 포켓몬의 번호와 개수를 기록한다.

 

2. HashMap의 key를 순회해서, ArrayList에 포켓몬 번호와 개수들을 다 넣고, 개수를 기준으로 오름차순 정렬한다.

 

3. 가져간 종류의 개수를 계산하면서, 종류의 개수가 N/2 이상이되면 리턴한다.

 

더 좋은 풀이

생각해보면, 종류의 개수와 상관없이 모두 1개를 가져가는 것이 매우 유리하다.

 

1. HashSet을 이용해서 포켓몬의 번호를 기록한다.

 

2. set의 크기는 종류의 개수이므로, N/2보다 작으면 set의 크기를 반환하고, 이상이라면 N/2를 가져간다.

 

소스코드

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int solution(int[] nums) {
        int n = nums.length;
        int selectNumber = n / 2;
        
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<int[]> infoList = new ArrayList<>();
        
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        for (int key : map.keySet()) {
            infoList.add(new int[] { key, map.get(key) });
        }
        
        Collections.sort(infoList, (o1, o2) -> {
            return o1[1] - o2[1];
        });
        
        int answer = 0;
        
        for (int[] arr : infoList) {
            if (selectNumber <= answer) {
                break;
            }
            
            answer += 1;
        }
        
        return answer;
    }
}

import java.util.HashSet;

class Solution {
    public int solution(int[] nums) {
        int n = nums.length;
        int selectNumber = n / 2;
        
        HashSet<Integer> set = new HashSet<>();
        
        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
            }
        }
    
        int size = set.size();
        
        return selectNumber > size ? size : selectNumber;
    }
}

 

실행결과

기존 풀이

더 좋은 풀이

성능 비교

구분	평균 실행 시간	평균 메모리 사용량
기존 풀이	3.59	83.98
더 좋은 풀이	0.68	81/05
변화율	-80.84%	-3.49%