프로그래머스 - [Level 3] 불량 사용자(JAVASCRIPT)

프로그래머스 불량 사용자[KAKAO]

카테고리 : 백 트래킹 / 순열조합

 조금은 까다로운 문제였다. 
로직을 크게 보면 다음과 같다.

1) 백트래킹으로 조건에 부합하는 경우의 수를 만든다.
2) set을 이용해 중복을 제거해준다.

아래 케이스로 테스트해보자.

user_id	 ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned_id ["fr*d*", "*rodo", "******", "******"]

1) 경우의 수
만들어지는 경우의 수는 아래와 같다.
---------------------------
 frodo crodo abc123 frodoc
 frodo crodo frodoc abc123
 fradi frodo abc123 frodoc
 fradi frodo frodoc abc123
 fradi crodo abc123 frodoc
 fradi crodo frodoc abc123
---------------------------
백트래킹으로 가능한 경우의 수를 전부 만들었다.(조합은 문자열에 저장)
단, 한 조합에 중복되는 원소가 없도록 했다.(visit 체크)

문제의 조건에서 순서와 관계 없이 모든 원소가 같다면 중복으로 처리한다고 했다.
그렇기 때문에 2)번 과정을 통해 중복을 제거해주어야한다.

2) 중복제거
 2)-1. String 으로 넘어온 조합의 값들을 배열로 바꿔준다.

 ex) str="frodo crodo abc123 frodoc"
 => arr=['fordo','crodo','abc123','frodoc']

 2)-2. 배열을 오름차순으로 정렬해준다.
    arr=[ 'abc123', 'crodo', 'frodo', 'frodoc' ]

 2)-3. 다시 배열을 스트링으로 만들어주고, set에 저장한다.
    newstr="abc123crodofrodofrodoc"

 2)-1 ~ 2)-3 의 과정을 거치면
 set에는 문제의 조건을 만족하는 경우의 수가 중복없이
 String 형식으로 저장된다.

따라서, set의 size를 return 하면 최종정답이 도출된다.

소스 코드

function solution(user_id, banned_id) {
    let answer = 0;
    let visit=[];
    let set=new Set();
    
    const check=(i,j)=>{
        for(let idx=0;idx<i.length;idx++){
            if(i[idx]!=='*' && i[idx]!==j[idx]) return false;
        }
        return true;
    }
   
    const makeList=(idx_i,count,str)=>{
        if(count===banned_id.length){
            let arr=str.split(" ");
            arr.shift();
            arr.sort();
            let newstr=arr.join("");
            set.add(newstr);
        } 
        if(idx_i>=user_id.length) return;
        
        for(let i=idx_i;i<banned_id.length;i++){
            for(let j=0;j<user_id.length;j++){
                /**
                	중복체크
                **/
                if(visit[j]) continue;
                /**
                    조건일치하지 않는 경우 무시
                **/
                if(banned_id[i].length!==user_id[j].length) continue;
                if(!check(banned_id[i],user_id[j])) continue;
                /**
                	백트래킹
                **/
                visit[j]=1;
                makeList(i+1,count+1,str+" "+user_id[j]);
                visit[j]=0;
            }
        }
    }
    
    makeList(0,0,"");
    return set.size;
}