프로그래머스 - 폰켓몬

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문제 출처

코딩테스트 연습 - 폰켓몬

[문제 설명]

박사님이 가지고 있는 포켓몬의 개수가 nums.length

내가 가지고 갈 수 있는 포켓몬 개수가 nums.length/2일 때,

제일 다양한 종류의 포켓몬을 가져가는 법.

피카츄,파이리,피카츄,피카츄 -> 2마리 뽑을 수 있음 -> 피카츄,파이리 -> 2종류가 최대

 

[처음 생각한 접근 방법]

총 N마리 = nums.length (학상 짝수) 1이상 10000이하
nums의 값은 포켓몬 종류 번호. 1이상 200000이하

가져갈 수 있는 포켓몬 수 = nums.length/2

최대한 다양한 종류의 포켓몬을 가져와야합니다.
피카츄, 피카츄, 파이리,피카츄면 -> 피카츄,파이리 2개.

1. HashMap에 key를 종류 value를 개수로 keySet을 읽어서 N/2개 채울 때까지 가져오기.

-> 포켓몬 각각의 개수는 그닥 필요 없어 보임.

2. 전체 개수와 뽑을 수 있는 개수의 상관 관계가 중요해보인다.
-> set에 넣고 set에서 N/2만큼만 뽑기

내가 생각하는 주의해야할점 : 종류가 N/2를 넘나 마냐가 중요할 거 같음.

 

뽑을 수 있는 개수가 종류의 개수보다 많으면 많이 뽑아봤자 종류는 한정되어 있어서 뽑을 수 있는 개수가 정답임.

전체 6개이므로 뽑을 수 있는 개수는 3개인데, 종류는 2개밖에 없음. 종류 2개가 정답.

 

 

반대로 종류의 개수가 뽑을 수 있는 개수보다 많으면 뽑을 수 있는 개수가 전부 다른 종류임.

종류는 6개이고 뽑을 수 있는 개수는 3개. 따라서 무조건 3개.

 

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        final int countLimit = nums.length/2;
        Set<Integer> set = new HashSet<>();
        
        //nums를 set에 넣는다.
        for (int num : nums) {
            set.add(num);
        }
        
        //set의 사이즈보다 countLimit가 같거나 크면 set의 사이즈가 정답.
        //set의 사이즈보다 countLimit가 작으면 countLimit가 정답.
        answer = set.size() <= countLimit ? set.size() : countLimit;

        return answer;
    }
}