폰켓몬 javascript - 프로그래머스

노요셉·2019년 10월 22일
0

PS

목록 보기
3/8

문제이해

제한 사항에 보면
nums 길이가 10000 이하의 자연수에요. 짝수이고요.
조합으로 뽑으려고 하면 2^10000은 >>>> 1억 ( 1초에 1억번 이하 연산한다면 시간복잡도가 나쁘지 않다고 가정한답니다. )

조합을 구현할 생각부터 하면 안됩니다.
왜 안되냐면 다음과 같은 조합을 사용한다면 maximum call stack 이란 에러메시지를 보게 되실거에요.

function combination(idx, rest){
	if( idx === n/2){
    	return 1;
  	}
    
    combination(idx+1,rest); // i번째 폰켓몬 안 뽑아요.
    combination(idx+1,rest-1); // i번째 폰켓몬 뽑아요.
}

combination(0, n/2);

로직

이 문제는 폰켓몬을 N/2개를 뽑을 수 있어요. 뽑았을때 최대의 폰켓몬의 수를 구하라는 문제입니다.

크게 두가지 경우가 있더라고요. 저는 자료구조를 set를 쓸게요. 그 이유는 언어가 달라도 표준 라이브러리들이 비슷하게 존재하기 때문에 다른언어에서도 크게 코드가 바뀌지 않아요. javascript만 하시면 그냥 {} 객체를 써도 되겠죠.
set를 쓰는 이유는 중복을 제거하려는 목적을 위해 사용합니다.
1. [2,2,2,2,3,3,3,3] 다음과 같은 상황에서는
set의 size: 2, nums의 배열길이 : 8, 뽑을 수 있는 폰켓몬 수 8/2
set의 크기보다 뽑을 수 있는 폰켓몬 수가 더 적을경우에는 set의 크기가 최대 폰켓몬의 수가 됩니다.
어떻게 아냐면 저도 몰라요. 입출력 예를 기반으로 시뮬레이션 했을때 그리 나오겠다 생각하고 풀었습니다.

  1. [1,1,2,2,3,3,4,4]
    set의 size: 4, nums의 배열길이 : 8, 뽑을 수 있는 폰켓몬 수 8/2
    set의 크기보다 뽑을 수 있는 폰켓몬 수가 같거나 많을경우에는 뽑을 수 있는 폰켓몬 수가 최대 폰켓몬의 수가 됩니다.

code

function solution(nums) {

    var answer = 0;
    let set = new Set();
    
    for(const number of nums){
        set.add(number);
    }
    
    console.log(`set = ${set.size}, num = ${nums.length/2}`)
    
    if( set.size < nums.length/2){
        answer = set.size;
    } else { 
        answer = nums.length/2;
    }

    return answer;
}

//n!/(n/2)!2!
profile
서로 아는 것들을 공유해요~

0개의 댓글