알고리즘 01.28

1. 완전탐색 소수찾기

function solution(numbers) {
 //중복 값 제거
 const primeNumbersCombi= new Set();   
 
 //n 중에, m개를 뽑은 조합을 찾는다.
 function getCombi(n, m){    
                let answer=[];
                const initialNumArr=numbers.split("");   
                const L= initialNumArr.length;
                //순회 했는지, 확인을 위한 ch 배열. 선택 된 아이템의 경우 제외하고 뽑는다. 
                let ch=Array.from({length:n},()=>0);
                //선택된 아이템을 담는다. 
                let tmp=Array.from({length:m}, ()=>0);
       
                function DFS(l, s){
                    if(l===m){
                      isPrime(Number(tmp.slice().join("")))
                      answer.push(tmp.slice()); 
                    }
                    else{
                        for(let i=0; i<n; i++){
                            if(!ch[i]) {tmp[l]=initialNumArr[i];
                            ch[i]=1;
                            DFS(l+1, i+1);
                            ch[i]=0;}
                        }
                    }
                }
                DFS(0, 0);
       
                return answer;
            }
  
 // 1개~L개의 아이템 조합을 뽑는다.  
 for(let i=1; i<=L; i++) {getCombi(L,i)}   
    
  // 소수를 찾는 함수 
    function isPrime(num){
        if(num===0 || num===1) return;
        if(num===2) {
          return primeNumbersCombi.add(num)
        }
        //효율성을 위해, 루트 이하 만큼만 순회한다. 
        for(let i=2; i<=Math.sqrt(num);i++){
            if(num%i===0) return;
        }
       return primeNumbersCombi.add(num)
     }
 
 return primeNumbersCombi.size
}

2. 완주하지 못한 선수

function solution(participant, completion) {
    const pMap=new Map();
    
    for(let i in participant){
        const a = participant[i];
        const b = completion[i];
        
         pMap.set(a,(pMap.get(a)||0)+1);
         b && pMap.set(b,(pMap.get(b)||0)-1);
    }
    
   for (let [key,val] of pMap){
       if (val ===1) return key;
   }
}

key-value 가 1:1 대응인 경우 사용할 수 있는 방법은 map 객체를 쓰는 것이다.(hashmap)
나는 object를 이용해 유사한 형태로 풀었는데, map 을 사용하는 방법이 정석인 것 같다. set(), get() 과 같은 내장 메서드도 사용할 수 있어서 좋다. 배열 형태로 [key, value] 가 들어가기 때문에 비구조화 할당을 해서 원하는 값을 꺼낼수도 있다.

for-in 과 for-of 를 헷깔린다. in은 in(dex)라고 외워두자. of 는 값을 가져온다.

3. 폰켓몬

function solution(nums) {
    let map =new Map();
    for(let i of nums){
       map.set(i, (map.get(i)||0)+1)
    }
    
   const mapSize = map.size;
   return Math.min(nums.length/2, mapSize)
   
}

같은 hashmap 문제이다. 위의 문풀에서 배운 내용을 다시 적용해서 풀어 보았다. size 라는 메서드로, length 를 따로 구하지 않아도 된다.

4. 같은 숫자는 싫어!

function solution(arr) {
const answer=[];

for(let i=0;i<arr.length;i++){
  if(arr[i]!==arr[i+1]) {
    answer.push(arr[i])
  }
 }
return answer;
}

간단한 stack,queue 문제! 앞의 숫자와 뒤의숫자를 차례로 비교하면서, 값이 다른 경우에만 push 해준다.

5. K번째 수

   let answer = [];
   for(let [start,end,idx] of commands){
       let a= array.slice(start-1,end);
       let b= a.sort((a,b)=>a-b);
       answer.push(b[idx-1]); 
    }
    
    
    return answer;

정렬 관련 문제. 구조분해 할당을 이용해 간단히 처리했다. array 관련 메서드들을 정리해놓으면 유용하다. slice, splice 가 대표적이다. slice(start idx, end idx)의 경우, 마지막 값은 포함하지 않는 것을 유의 해야한다. splice(startidx, 갯수)는, 배열의 값을 더하거나, 지우거나, 교체할때 유용하다.