프로그래머스 불량사용자

문제

풀이

크게 두 가지 작업으로 나뉜다.
1. 정규식을 통한 문자열 체크
2. 백트래킹을 통한 유저아이디와 차단아이디의 매칭

나누어서 살펴보면
먼저 차단당한 아이디들의 * 문자를 . 문자로 바꾸고 ^와 $를 앞뒤에 붙여줌으로써 정규식에 사용하기 편한 형태로 바꿔준다.

  for(let i=0;i<banned_id.length;i++){
      banned_id[i] = '^'+banned_id[i].replace(/\*/g,'.')+'$';
  }

그 후 백트래킹 과정에서 match를 통해 사용자의 아이디와 차단당한 아이디를 비교하여 포함될 수 있는 아이디인지 체크해주었다.

  for(let i=0;i<user_id.length;i++){
    if(!vi[i] && user_id[i].match(banned_id[idx])){
      vi[i]=true;
      cnt+=btrc(user_id,banned_id,vi,record,idx+1);
      vi[i]=false;
    }
  }

또, 차단 가능성이 있는 아이디 리스트는 문자열로 바꾸어 딕셔너리에 저장함으로써 두번 카운트 하지 않도록 체크해주었다.

  if(idx==banned_id.length) {
    let temp='';
    for(let i=0;i<user_id.length;i++){
      if(vi[i]) temp+=i;
    }
    if(!(temp in record)) {
      record[temp]=1;
      return 1;
    }
    else return 0;
  }

소스코드

function btrc(user_id,banned_id,vi,record,idx){
  if(idx==banned_id.length) {
    let temp='';
    for(let i=0;i<user_id.length;i++){
      if(vi[i]) temp+=i;
    }
    if(!(temp in record)) {
      record[temp]=1;
      return 1;
    }
    else return 0;
  }

  let cnt=0;
  for(let i=0;i<user_id.length;i++){
    if(!vi[i] && user_id[i].match(banned_id[idx])){
      vi[i]=true;
      cnt+=btrc(user_id,banned_id,vi,record,idx+1);
      vi[i]=false;
    }
  }
  return cnt;
}

function solution(user_id, banned_id) {
  let vi = new Array(8).fill(false);
  let record={};
  for(let i=0;i<banned_id.length;i++){
      banned_id[i] = '^'+banned_id[i].replace(/\*/g,'.')+'$';
  }
  
  return btrc(user_id,banned_id,vi,record,0);
}

console.log(solution(["frodo", "fradi", "crodo", "abc123", "frodoc"],["fr*d*", "*rodo", "******", "******"]));

후기

정규식과 백트래킹 알고리즘에 대해 알고 있다면 풀 수 있는 문제였다. 하지만 알고있더라도 연습이 되어있지 않다면 푸는데 제법 시간이 걸릴 것 같다.