[Javascript/Algorithm] 프로그래머스 — 불량 사용자 (Lv.2)

#순열 #조합

문제 설명

• 이벤트에 응모한 전체 사용자 아이디 목록 user_id
• 개인정보 보호를 위해 사용자 아이디 중 일부 문자를 ‘*’ 문자로 가려서 저장한 불량 사용자 아이디 목록 banned_id
• 사용자 아이디 목록에서 불량 사용자 아이디 목록에 매핑된 응모자 아이디를 제제 아이디라고 한다
• 이벤트 당첨에서 제외되어야 할 제재 아이디 목록으로 가능한 경우의 수가 몇 가지 있는지 구해야 한다

문제 해결 방식 (내 생각)

• 제재 아이디 후보로 가능한지 확인하느 함수 isPossible 구현
• banned_id에 저장된 불량 사용자 아이디를 하나씩 확인하면서, user_id에서 불량 사용자 아이디와 일치하는제재 아이디후보를 possible_id배열에 저장
• possible_id를 이용해 가능한 조합의 수를 구한다

내 코드 (오답)

// 제재 아이디 후보로 가능한지 확인하는 함수
const isPossible = (uId, bId) => {
    // 1. 문자열 길이 비교
    if (uId.length !== bId.length) return false;
// 2. 값이 '*'이 아닌 자리의 문자가 모두 같은지 확인
    let cnt = 0;
    for (let i = 0; i < uId.length; i++) {
        if (bId[i] !== '*' && uId[i] !== bId[i]) return false;
    }
    return true;
}
function solution(user_id, banned_id) {
    let answer = 0;
    const len = banned_id.length;
    const possible_id = Array.from({length: len}, () => []);    // 제재 아이디 후보를 저장하는 배열
    
    banned_id.forEach((bId, idx) => {
        user_id.forEach(uId => {
            if (isPossible(uId, bId)) possible_id[idx].push(uId);
        });
    });
    console.log(possible_id);
    
    const DFS = (idx, arr) => {
        if (idx === len) {
            if (arr.length === len) answer++;
            return;
        }
        else {
            for (let i = 0; i < possible_id[idx].length; i++) {
                if (arr.indexOf(possible_id[idx][i]) === -1) {
                    /* arr에 제재 아이디를 넣는 과정 */
                }
            }
        }
    }
    DFS(0, []);
    
    return answer;
}

테스트케이스 3번

banned_id가 [“fr*d*”, “*rodo”, “******”, “******”] 일 경우 각 인덱스에 들어갈 수 있는 제재 아이디 목록을 possible_id에 저장하면 다음과 같다.

[ [ ‘frodo’, ‘fradi’ ], [ ‘frodo’, ‘crodo’ ], [ ‘abc123’, ‘frodoc’ ], [ ‘abc123’, ‘frodoc’ ]]

여기서 각 인덱스에서 원소를 한 개씩 뽑는 모든 조합을 구하고, 중복을 제거하면 정답을 구할 수 있지 않을까 생각했다. DFS를 이용해서 조합수를 구하는 것, Set 객체를 사용함으로써 중복된 배열 조합을 없애면 될 것 같다고 생각했지만, 마저 구현을 하려고 보니 for문이 너무 많이 반복되고 풀이가 점점 비효율적이게 되는 것 같았다.

결국 다른 사람 풀이를 참조해서 아예 갈아 엎었다.

최종 풀이

// 제재 아이디 후보로 가능한지 확인하는 함수
const isPossible = (uId, bId) => {
    // 1. 문자열 길이 비교
    if (uId.length !== bId.length) return false;
// 2. 값이 '*'이 아닌 자리의 문자가 모두 같은지 확인
    let cnt = 0;
    for (let i = 0; i < uId.length; i++) {
        if (bId[i] !== '*' && uId[i] !== bId[i]) return false;
    }
    return true;
}
function solution(user_id, banned_id) {
    const ch = Array.from({length:user_id.length}, () => 0);
    const set = new Set();
    
    const DFS = (idx, cnt, possible) => {
        if (cnt === banned_id.length) {
            let arr = possible.split(' ');
            arr.shift(); // 맨 앞에 저장된 '' 값 제거
            arr.sort();
            let newStr = arr.join('');
            set.add(newStr);
        }
        if (idx >= user_id.length) return;
        
        for (let i = idx; i < banned_id.length; i++) {
            for (let j = 0; j < user_id.length; j++) {
                if (ch[j] === 1) continue;
                if (!isPossible(user_id[j], banned_id[i])) continue;
                ch[j] = 1;
                DFS(i+1, cnt+1, possible + ' ' + user_id[j]);
                ch[j] = 0;
            }
        }
    }
    DFS(0, 0, '');
    
    return set.size;
}

• DFS와 백트래킹을 이용해서 풀어야 한다
• ch 배열을 통해 이미 사용한 user_id 값인지 체크해서 조합 구하기

어떻게 이렇게 간단하고 이해하기 쉽게 풀 수 있는거지?

아무튼 나는 아직 갈 길이 멀다는 것을 느꼈다. ^_ㅠ

출처: https://gwang920.github.io/algorithm/progreammers-2-64064/