알고리즘 - (폰켓몬)

• 문제 출처 : 프로그래머스
• 문제명 : 폰켓몬
• 분류 : '찾아라 프로그래밍 마에스터'에 분류되어있음
• 언어 : Java
• 체감 난이도 : ⭐⭐
• 풀이 시간 : 40min
• Fail Cnt : 1 (잘못된 문제 접근)

---

---

첫번째 제출(Fail : 시간초과)

1. 접근 방식 및 알고리즘

: 모든 경우의 수에 대해 N/2를 순회한다. 순회하면서 새로운 종류의 폰켓몬일 경우 카운팅하며 이를 바탕으로 선택할 수 있는 최대 폰켓몬의 종류를 알아낸다.

---

2. 코드 및 프로세스

전역변수

    int[] g_poncket = new int[200001];	//순회한 폰켓몬의 종류는 1로 저장, 0일경우 순회하지 않은 폰켓몬 종류임을 의미
    int[] g_visit = new int[10001];	//DFS탐색시 인덱스 방문 여부를 저장(0:방문안함, 1:방문)
    int maxCnt = 0;	//선택할 수 있는 최대 폰켓몬의 종류를 저장

void get_max_kinds(int[] nums, int idx, int cnt, int kindsCnt); 메소드

    /**
     * 재귀호출을 통해 N/2마리의 폰켓몬을 순회한다
     * @param nums 입력으로 받은 폰켓몬
     * @param idx 현재 방문할 인덱스
     * @param cnt 여태까지 순회한 폰켓몬의 수 ( 호출시 순회하는 폰켓몬을 포함함 )
     * @param kindsCnt 순회하면서 선택한 폰켓몬의 종류 수
     */
         void get_max_kinds(int[] nums, int idx, int cnt, int kindsCnt) {
        g_visit[idx] = 1;
        int flag = 0;   //원래 순회했던 포켓몬 종료이면 1로 저장

        if(g_poncket[nums[idx]] == 0) { //해당 포켓몬 종류를 순회한적 없으면
            g_poncket[nums[idx]] = 1;
            kindsCnt += 1;	//폰켓몬 종류수를 +1
        } else {	//이미 해당 폰켓몬 종류를 순회한적 있으면
            flag = 1;
        }

        int N = nums.length;

        if(cnt < N/2) {	//재귀호출부(순환부)
            for(int i=idx+1; i<N; i++) {
                if(g_visit[i] == 0) {
                    get_max_kinds(nums, i, cnt+1, kindsCnt);
                }
            }
        } else {	//종료부
            if(cnt == N/2) {
                if (kindsCnt > maxCnt) {	//최대 폰켓몬의 종류로 업데이트
                    maxCnt = kindsCnt;
                }
            }
        }

        if(flag == 0) {	//이번 재귀호출로 폰켓몬 종류수가 +1 되었다면 원상복구한다
            g_poncket[nums[idx]] = 0;
        }

        g_visit[idx] = 0;	//방문처리 원상복구
    }

public int solution(int[] nums) 메소드

: N/2의 폰켓몬을 방문하는 get_max_kinds 메소드를 호출하고 정답을 출력한다

    public int solution(int[] nums) {
        int answer = 0;

        for(int i=0; i<nums.length; i++) {
            get_max_kinds(nums, i, 1, 0);
        }

        answer = maxCnt;

        return answer;
    }

---

3. 결과

: 프로세스 오류는 없으나 시간초과. DFS순회가 아닌 다른 방식으로 문제를 접근해야함을 느꼈음.

---

---

두번째 제출(Success)

1. 접근 방식 및 알고리즘

1) 입력으로 들어온 폰켓몬들의 종류에 대해, 종류당 몇마린지 카운팅하는 배열을 사용했다.

Ex) nums = [3,3,3,2,2,4] 일 경우

값\인덱스(폰켓몬종류)	0	1	2	3	4	5	...
	0	0	2	3	1	0

2) 배열을 위와 같이 저장하고 내림차순 정렬하면 최소 한마리 이상인 종류들의 값이 배열의 앞에 위치하게 된다. (이때 인덱스는 폰켓몬 종류와 상관없게 됨을 주의)

값\인덱스	0	1	2	3	4	5	...
	3	2	1	0	0	0	0

3) 선택할 수 있는 최대 폰켓몬의 수를 구하면 되므로 앞에서부터 N/2개까지(인덱스: 0~(N/2-1)) 값이 0이 아니면 카운팅한 것이 정답이된다.

---

2. 코드

    public int solution(int[] nums) {
        int answer = 0;
        Integer[] cntArr = new Integer[200001];

        Arrays.fill(cntArr, 0);

        //각 종류당 몇마리 있는지 저장
        for(int i=0; i<nums.length; i++) {
            cntArr[(nums[i])]++;
        }

        //내림차순으로 정렬
        Arrays.sort(cntArr, Collections.reverseOrder());

        for(int i=0; i<nums.length/2; i++) {
            if(cntArr[i] == 0) { break;}
            answer++;
        }

        return answer;
    }

---

3. 결과 및 주의점

배열을 내림차순으로 정렬하기 위해 Integer형으로 배열을 만들고 Collections.reverseOrder() 메소드를 사용함. Integer는 기본 자료형이 아닌 객체이기 때문에 Arrays.fill(cntArr, 0); 을 사용해 반드시 값을 저장해야 한다. (안할경우 nullpointerexception 발생)

이와 관련된 Wrapper 클래스 내용은 추후에 정리할 예정