[21/10/26 KATA NINJA] 불량 사용자

16417 단어 codekatacodekata

내 코드

function solution(user_id, banned_id) {
    let answer = 0;
    
    const memo = [];
    
    const r = banned_id.length;
    
  // 밴의 수만큼 순열을 구한다.
    const per = DFS([...user_id],r);
  
  //순열을 순회하면서 ban되면서 중복이 아닌 요소를 찾을때마다 카운트를 1 올려준다.
    per.forEach((p)=>{
        
        const target = [...p].sort().join("");
        
      
      	// ban이면서 중복이 아닌 경우 answer을 늘려준다.
        if(isBan(p) && !memo.includes(target)){
            memo.push(target);
            answer++;
        }
    })
    
    return answer;
    
  // 순열 코드이다.
    function DFS(array, r){
        
        if(r === 1){
            return array.map((str)=>[str])
        }
        
        const target = [];
        
        for(let i=0;i<array.length;i++){
            const cur = array[i];
            
            const res = DFS([...array.slice(0,i),...array.slice(i+1)],r-1);
            
            res.forEach(item => {
                target.push([cur,...item]);
            })
        }
        
        return target;
    }
  // 밴을 체크한다.
    function isBan(p){
      // 같은 색인 요소들을 비교하여 하나라도 해당되지 않는다면 , 그 순열 요소는 유망하지 않다.
        for(let i=0;i<banned_id.length;i++){
            const cur = p[i];
            const target = banned_id[i];
            
          // 길이가 다르면 false이다. 해당 순열 자체가 유망하지 않다.
            if(cur.length !== target.length){
                return false;
            }
          // *이 아니면서 다르다면, 다른 문자열인 것이므로 해당 순열은 유망하지 않다.  
            for(let j=0;j<cur.length;j++){
                if(cur[j] !== target[j] && target[j] !== '*'){
                    return false;
                }
                
            }
        }
        return true;
    }
        
   
}

  • 중복 체크하는데 배열 메소드를 사용하고 있음. map을 사용하여 중복을 체크해보자 (속도 개선을 위해)

  • banned_id 요소와 순열 요소 간 문자열 비교 개선할 수 있을것같다?

일부 개선 코드

 const memo = new Map();
    ...
    per.forEach((p)=>{
        
        const target = [...p].sort().join("");
        
        if(isBan(p) && !memo.get(target)){
            memo.set(target,true); 
            answer++;
        }
    })

	const memo = {};
    
...
    
    per.forEach((p)=>{
        
        const target = [...p].sort().join("");
        
        if(isBan(p) && !memo[target]){
            memo[target] = true;
            answer++;
        }
    })

개선이 되지 않았다..? 배열자체도 객체이기 때문에 큰 차이가 없는 것으로 파악

좋은 웹페이지 즐겨찾기