[Refresh ! 코딩 테스트 / js] 216. Combination Sum III &&

문제풀이

• dfs 으로 풀수도 있고 제귀로 풀수도 있는 기본 문제이다..
• 딱히.. 해석 & 머리 고민할게 없었다...

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    //이거 그냥..뭐.. 완전 탐색 기본 문제임
    //그니까 1부터 n 까지 배열을 만듬 그다음 선택했는데 이거되냐? 라는 식으로 그냥 가도됨
    let array_combination = Array.from({ length: 9 }, (_, index) => index + 1); 
  let answer=[];
   function combination(chose_n,sum,new_arr,index){
     //이거 그냥 sum 으로 가자 귀찮네... 까먹어버림..;; 
    
     if(sum>n) return;
     // 어쩌피 안되는거니까 return 해주세요..
   
     if(chose_n>=k) {
        // 정확히 선택했어요
        if(sum==n) answer.push(new_arr);
        return;
     }
     for(var i=index; i<9; i++){
        //여기서하나 선택하세요 
        combination(chose_n+1,sum+array_combination[i],[...new_arr,array_combination[i]],i+1)
     }

   }

    combination(0,0,[],0)
    return answer;
  }

문제풀이

• 문제풀이라고 할게있나... 그냥 바이너리 풀이이다..

/**
 * @param {number[]} spells
 * @param {number[]} potions
 * @param {number} success
 * @return {number[]}
 */
var successfulPairs = function(spells, potions, success) {
  //[1 3 5] [1 2 3 4 5] suscess 7 일때 글쿤 바이너리 서치 맞음
  let answer=[];
  potions.sort((a,b)=>a-b)
   for(var i=0; i<spells.length; i++){
    let left=0;
    let right= potions.length-1;
    while(left<=right){
        let mid= Math.floor((left+right)/2);
        // 가운데를 구함 
        if(spells[i]* potions[mid]>=success){
            right=mid-1;
        }
        else{
        left= mid+1;
        }
    }
    
    answer.push(potions.length-left);
   }
return answer;
};