[프로그래머스] 2019 카카오 개발자 겨울 인턴십 - 불량 사용자(JavaScript)

heumheum2·2020년 5월 7일
0

코딩테스트

목록 보기
3/5
post-thumbnail

📚 문제

이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견했습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하려고 합니다. 이 때 개인정보 보호를 위해 사용자 아이디 중 일부 문자를 * 문자를 사용하였습니다.
불량 사용자 목록에 매핑된 응모자 아이디를 제제 아이디라고 부르기로 했습니다.

예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면

|응모자 아이디|
|:-----|
|frodo|
|fradi|
|crodo|
|abc123|
|frodoc|

다음과 같이 불량 사용자 아이디 목록이 전달된 경우,

|불량 사용자|
|:-----|
|fr*d*|
|abc1**|

불량 사용자에 매핑되어 당첨에서 제외되어야 할 제제 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.

|제제 아이디|
|:-----|
|frodo|
|abc123|

|제제 아이디|
|:-----|
|fradi|
|abc123|

이 처럼 제제 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

📖 풀이

let result = 0;
const memo = [];

function solution(user_id, banned_id) {
    const banned_list = banned_id.map(bannedId => bannedId.replace(/\*/g,'.'));
    const visit = [...user_id].fill(false);
    dfs(user_id, banned_list,0, 0, visit);
    return result;
}

function dfs(user_id, banned_id, idx, n, visit){
    const visited = [...visit];
    const regex = RegExp(`\^${banned_id[idx]}\$`);
    
    if(n === banned_id.length){
        const temp = [];
        visited.forEach((v,i) => v && temp.push(user_id[i]));
        
        let cnt = 0;
        memo.forEach(array => {
            let flag;
            for(let i = 0 ; i < temp.length ; i++){
                flag = array.some(element => element === temp[i]);
                if(!flag){
                    break;
                }
            }
            !flag && cnt++;
        });
        if(cnt === memo.length){
            memo.push(temp);
            result++;
        }
        return;
    }
    
    user_id.filter((id, index) => {
        if(regex.test(id)){
            if(!visited[index]){
                visited[index] = true;
                dfs(user_id, banned_id, idx+1, n+1, visited);
                visited[index] = false;
            }
        }
    });
}

생각보다 오래 걸렸던 문제입니다. 불량사용자의 아이디 목록을 가지고, 응모자 아이디를 매칭하여 제외를 시키는 문제였습니다.
불량사용자에 *은 문자 하나 이상을 포함하고 있는데 여기서 *.으로 만들어 하나 이상의 문자를 포함하도록 만드는 정규식을 이용해 응모자 목록에 매칭을 해야겠다고 생각했습니다. 매칭을 할 때, 하나하나 다 탐색을 해야하니 완전탐색 알고리즘을 사용해야하는데 그 중 **깊이우선탐색(DFS)**을 이용해 문제를 해결했습니다.

📃 링크

2019 카카오 개발자 겨울 인턴십 - 불량 사용자

profile
커피가 본체인 개발자 ☕️

0개의 댓글