Programmers : 불량 사용자

풀이 요약

regex, 순열

풀이 상세

1. 해당 문제의 중요한 점은 3가지 이다.

   • 임의의 아이디가 불량 사용자에 해당하는 지를 찾아내야 한다. 나의 경우 regex 를 활용하였다.
   • 제제 아이디는 오직 하나의 불량 사용자만 찾아낸다. 이 말은 즉 한 제제 아이디로 여러 응모자가 해당될 수도 있으나, 오직 한 경우에 한번만 사용하겠다는 의미이다.
   • 중복된 경우의 수가 나타나는 경우는 어떤 방법으로 해결할지를 찾아야 한다.

2. regex 는 다음과 같은 식으로 구성하였다.

   • * 을 \w{1} 로 반환한다. 단 이스케이프 문자를 문자열에 집어넣기 위해서는 \\w{1} 로 표시한다. 문자열도 가능은 하지만 혹시나 모를 사태를 위해 나는 RegExp 인스턴스로 반환을 해주었다.
   • 여기에 좀 더 강력한 일치를 위해 ^(식)$ 의 형태로 구성한다. ^ , $ 은 시작과 끝을 나타내며, () 는 그룹을 의미한다. 예를 들어 fr*d* 는 ^(fr\w{1}d\w{1})$ 로 치환된다.
     해당 식은 fr과 - 영어&숫자 1개 - d - 영어&숫자 1개 의 형태로 시작하여 바로 문자가 끝이나는 문자를 반환한다.

3. 제제 아이디 당 하나의 불량 사용자를 찾는 방법은 순열을 사용하는 것이다. 순서가 다른 $nPm$ 의 경우의 수 가운데, regex 의 순서를 통해 통과하는 경우만 포함시켜 진행한다.

4. 그럼에도 중복은 발생할 수 있다. 왜냐면 제제 아이디 id 형태가 동일한 것이 들어있을 수 있기 때문이다. (테케 2,3 참고)
   중복되는 id 형태가 있어 나타나는 중복된 경우의 수를 해결하기 위해 배열을 정렬한 뒤 문자열로 치환하여 Set 에 집어넣었다. 이로써 동일한 경우가 반환되는 문제를 해결 할 수 있다.

배운점

• 자바스크립트의 문자열의 문자열 연산 과정에서 이스케이프 문자가 제대로 반영되지 않는 상황이 발생할 수 있다. 예를들어 abc\\w 는 abc\w 가 될 수 있지만 abc + \\w 의 경우에는 abc\\w 로 나오더라.

let [regex_arr,ans] = [[], new Set()];
function swap(user_id,a,b) {
    let temp = user_id[a];
    user_id[a] = user_id[b];
    user_id[b] = temp;
    return 1;
}

function perm(user_id,N,d) {
    if(d == N) {
        ans.add(user_id.slice(0,N).sort().toString());
        return 1;
    }
    for(let i=d; i<user_id.length; i++) {
				regex_arr[d].test(user_id[i]) && swap(user_id,d,i) && perm(user_id, N, d+1) && swap(user_id,d,i);
		}
    return 1;
}

function solution(user_id, banned_id) {
    regex_arr = banned_id.map((item)=> new RegExp(`^(${item.split("").map((item)=> item=="*" ? "\\w{1}" : item).join("")})$`));
    perm(user_id, banned_id.length, 0);
    return ans.size;
}