프로그래머스 Lv.2) 폰켓몬(포켓몬, Pokemon)

폰켓몬

프로그래머스

풀이

 이 문제 역시 스킬 체크를 풀다가 나왔다. 보자마자 최근 많이 풀고있던 이분탐색(이진탐색, Binary Search)라는 것을 눈치챘고, 포켓몬 타입의 수가 리턴값이기 때문에 left, right, mid도 쉽게 정할 수 있었다. 그나마 생각할 시간이 조금 필요했던 부분은 이 기준을 어떻게 이용해서 값을 얻을 것이냐였다. 내가 찾은 답은 타입의 종류를 담은 배열을 만들어 중복 체크를 하는 것이었다. 1~200,000까지 분류 번호가 된다는 조건이 있어서 배열을 200,001만큼 초기화 시켜줬다.

반복문을 통해 서로 다른 타입의 수를 count하다가 mid이상이 되면 mid가 최대값이 아니라는 뜻이기 때문에 left값을 늘려 mid 값을 증가시켜주고, 서로다른 포켓몬 수가 mid만큼도 안되면 right를 줄여 값을 좁혀줬다. 

 

코드

public class PokeMon_1845 {
    final static int MAX_SIZE = 200001; // 1~ 200000만

    private static int solution(int[] nums) {
        return binarySearch(nums);
    }

    private static int binarySearch(int[] nums) {
        int left =0;
        int right = nums.length/2;  // 최대 가져갈 수 있는 타입 수
        int answer =0;

        while(left <= right) {
            int mid = (left+right)/2;   // 가져갈 수 있는 타입 수 답

            if(checkTypes(nums, mid)) {
                left = mid+1;
                answer = mid;
            } else {
                right = mid-1;
            }
        }
        return answer;
    }

    private static boolean checkTypes(int[] nums, int mid) {
        int cnt=0;

        int[] check = new int[MAX_SIZE];

        for(int num : nums) {
            if(cnt >= mid) { // 충분하다, 이상
                return true;
            }
            if(check[num] ==0) {
                check[num] =1;
                cnt++;
            }
        }
        return cnt >= mid ? true : false;
    }
    public static void main(String[] args) {
        int[] nums = {3,1,2,3};

        System.out.println(solution(nums));
    }
}