문제 요약

불량 사용자가 있는데 불량사용자는 아이디를 가리기 위해 *로 몇개 가려서 나온다. 불량 사용자 리스트와 , 일반 사용자 리스트가 있을때
불량 사용자를 추측해서 경우의 수가 몇개 나오는지 리턴하면 된다.

문제 풀이

처음에 그냥 문제를 풀었는데 for문을 3번 사용해야 해서 머리가 아팠다.
과연 성능을 통과할수 있을지 고민했지만 continue, break 조건을 많이 걸어서 괜찮을거라 판단했다.
DFS 를 이용해서 완전탐색을 진행했다.

내가 푼 풀이

function solution(user_id, banned_id) {
    var answer =  new Set();
   let visitied = Array.from({length:user_id.length},()=>true);
  let nowIdx =0;
  DFS(nowIdx,[]);
  function DFS(idx,arr){
       
    if(idx>=banned_id.length){
  
      let endArr = arr.slice(0);
      endArr.sort();
      answer.add(JSON.stringify([...endArr]))
      return;
    }
    let targetBid = banned_id[idx];
    for(let i=0; i<user_id.length;i++){
      let uId = user_id[i];
      if(uId.length!==targetBid.length || !visitied[i]){
        continue;
      }
      for(let j=0; j<uId.length+1;j++){
        let uIdLetter = uId[j];
        let bIdLetter = targetBid[j];
        if(bIdLetter==='*'){
          continue;
        }
        if(uIdLetter!==bIdLetter){
          break;
        }
        if(j===uId.length){
        
          visitied[i] = false;
          arr.push(uId);
       
          DFS(idx+1,arr)
       
          arr.pop();
          visitied[i] = true;
        }
      }
      
    }
    
  }
  


  
    return answer.size;
}

예전 문제 여서 그런지 (2019년도 문제) 성능 테스트가 딱히 있지는 않았다.

그래도 몇개 빼고 결과는 빠르게 나왔다.

통과~~ 완전 탐색에 대해서 계속 풀다보니 이제 잘 알게 되었다.ㅎㅎ

new Set 을 이용해서 중복을 제거 하려고 했는데 배열은 내부의 값을 비교하지 않기 때문에 JSON.stringify 로 스트링으로 변화해줘서 중복을 제거할수 있었다.