javascript - 폰켓몬

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/1845

코딩테스트 연습 - 폰켓몬

input으로 숫자 배열이 주어진다. 배열의 숫자는 폰켓몬의 종류를 의미하고, 우리는 nums/2 만큼의 폰켓몬을 고른다.

고른 폰켓몬 중에 최대로 많은 종을 뽑는 경우의 숫자를 리턴하는 문제이다.

 

문제 결과

 

입출력 예 #2
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

 

 

문제를 처음 봤을 때 가장 먼저 떠오른게 뽑을 수 있는 모든 경우를 탐색해야한다는 것이였다.

level1 문제인데 왜 그렇게 어렵게 접근했는지 모르겠다.

그래서 DFS를 사용해서 뽑을 수 있는 모든 경우를 탐색하여 가장 최대로 나오는 종류의 수를 구했다.

예시는 모두 통과했지만, 채점을 돌렸을 때 시간초과에 걸렸다.

 

nums의 길이가 10000이하의 자연수인데, 시간 초과에 걸리는 것은 당연한 결과였다.

nums의 길이(N)는 1 이상 10,000 이하의 자연수이며

 

문제의 코드

var size;
var num_arr;
var answer = 0;

function solution(nums) {
    num_arr = nums;
    size = parseInt(nums.length / 2);     
    selectMon(0, []);
    return answer;
}

function selectMon(index, selected) {
        // 뽑힌 폰켓몬의 수가 size와 같을 때
        // 종류 개수 판단 후 리턴
        console.log(index, selected);
        if(selected.length === size) {
            const set = new Set(selected);
            const uniqueArr = [...set];
            selected.pop();
            if(answer < uniqueArr.length)   answer = uniqueArr.length;
            return 0;
        }
        if(index === num_arr.length)   return 0; 
        selected.push(num_arr[index]);
        selectMon(index+1, selected);   
        selected.pop();
        selectMon(index+1, selected);
    }

테스트케이스 6번부터 시간 초과에 걸림..

 

생각해보니까 주어진 nums 배열을 set으로 변환하여 중복된 종을 모두 제거한 뒤

걸러진 폰켓몬의 종의 수가 nums.length/2 보다 크거나 같으면 우리는 모두 다른 종을 뽑을 수 있고

작으면 걸러진 폰켓몬의 종의 수가 답이 된다는 것을 알게 되었다.

 

이렇게 간단한 문제를😭

어떻게 하면 문제의 요구사항을 쉽게 접근할 수 있을지 많이 연습해야겠다.

 

javascript에서 array to set

• set = new Set(array)

set to array

• array = [...set]

function solution(nums) {
    var answer = 0;
    const set = new Set(nums);
    const dup_del = [...set];
    if(dup_del.length > nums.length/2)  answer = nums.length/2;
    else    answer = dup_del.length;
    return answer;
}