[프로그래머스] 불량 사용자 (javascript)

https://school.programmers.co.kr/learn/courses/30/lessons/64064

프로그래머스

접근 방법

먼저 문제 유형부터 파악하기가 어려웠다. 지금까지 봐았던 dfs 문제가 아니기 때문이였는데 다음 사항 때문에 완전탐색이라고 생각하게 되었다

• banned_id에 일치하는 user_id value 값을 찾는 과정에서 단계가 넘어가도 반복적인 코드가 발생한다.
  banned_id[0]을 user_id를 순회하면서 찾게 되면 다음 banned_id[1]에서도 똑같이 반복
• banned_id 배열의 길이만큼 경우의 수를 찾으면 반환한다.

풀이 방법

1. dfs 함수를 만들고 인자로 현재 user_id와 비교 할 banned_id의 단계(level)과 경우의 수를 담는 temp 객체를 보내준다.
2. level이 banned_id의 길이와 같을 경우 함수를 return 하고 중복을 방지하기 위해 temp를 정렬하고 문자열로 바꾸어 저장한다.
3. 2번의 경우와 같지 않을 경우 user배열과 현재 banned_id[level] 과 비교하며 문제의 조건대로 이행한다
   1. banned_id[level][index] 가 *일 경우에는 pass
   2. user index와 ban index를 비교했을 때 같지 않은 경우 false를 반환하고 break 한다.
4. false를 반환하지 않고 끝까지 왔다면 temp 객체안에 현재의 user 정보가 들어있는지 확인 후 없을 경우에 temp객체에 user 정보를 담고 다음 level banned_id를 비교하기 위해 dfs함수를 호출한다.

function solution(user_id, banned_id) {
    var answer = new Set();
    
    function dfs(level, temp) {
        if(level === banned_id.length) {
            answer.add(Object.keys(temp).sort().join(','))
            return
        }
        for(let user of user_id) {
            let flag = true
            if(user.length !== banned_id[level].length) continue
            for(let i = 0; i < user_id.length; i++) {
                if(banned_id[level][i] === '*') continue
                if(user[i] !== banned_id[level][i]) {
                    flag = false
                    break
                }
            }
            if (flag && !temp[user]) {
                temp[user] = true
                dfs(level + 1, temp)
                delete temp[user]
            }
        }
    }
    
    dfs(0, {})

    return answer.size;
}

틀린 풀이

틀린 이유에 대해 생각해 봤을 때 일반적으로 dfs 함수를 만들 때 미로 찾기 같은 문제유형을 풀면서 감에 의존했었던 것 같다.

dfs 함수를 만든다는 것은 재귀함수를 호출하는 기준과 상태를 저장하는 것이라고 생각한다.

미로 찾기에서는 현재 칸에서 일어나야 할 일을 함수에 작성하고, 재귀함수를 호출할 때는 현재칸에서 다른 칸으로 움직일 때의 조건을 써주게 된다.

이번 문제의 경우도 banned_id의 현재 조건을 만족하는 user_id의 값을 찾고나면 다음칸으로 이동하는 것과 같다. 그렇기 떄문에 banned_id의 현재 인덱스를 기준으로 다음 인덱스로 움직일 떄의 조건을 작성하면 되는 문제이다.

현재의 기준을 제대로 생각해보지 않아 다음과 같은 코드가 발생했다.

function solution(user_id, banned_id) {
    var answer = new Set();
    
    function dfs(level, temp) {
        if(level === banned_id.length) {
            answer.add(Object.keys(temp).sort().join(','))
            return
        }
   
       for(let level = level; level < banned_id.length; level++) {
        for(let user of user_id) {
            let flag = true
            if(user.length !== banned_id[level].length) continue
            for(let i = 0; i < user_id.length; i++) {
                if(banned_id[level][i] === '*') continue
                if(user[i] !== banned_id[level][i]) {
                    flag = false
                    break
                }
            }
            if (flag && !temp[user]) {
                temp[user] = true
                dfs(level + 1, temp)
                delete temp[user]
            }
        }
      }
    }
    
    dfs(0, {})

    return answer.size;
}

다른 풀이

chat gpt에게 피드백을 받아서 풀어본 풀이이다.

나의 풀이와 비교했을 때 몇가지 다른점이 발생한다.

• 어차피 경우의 수 즉 개수를 구하는 것이기 때문에 정확한 조건에 충족한 user 값이 아닌 user의 인덱스를 넣어줌으로써 좀 더 set함수를 이용하기 쉽게 작성하였다.
• 일치하는 조건을 isMatched함수로 따로 빼내어 가독성을 높였다.
• selected는 배열이기 때문에 직접적으로 sorting 하는 것이 아닌 새로운 배열을 만든다. 

function solution(user_id, banned_id) {
    var answer = new Set();

    function dfs(level, selected) {
        if (level === banned_id.length) {
            answer.add([...selected].sort().join(','));
            return;
        }

        for (let i = 0; i < user_id.length; i++) {
            let user = user_id[i];
            let banned = banned_id[level];

            if (!selected.has(i) && isMatched(user, banned)) {
                selected.add(i);
                dfs(level + 1, selected);
                selected.delete(i);
            }
        }
    }

    function isMatched(user, banned) {
        if (user.length !== banned.length) return false;
        for (let i = 0; i < user.length; i++) {
            if (banned[i] !== '*' && user[i] !== banned[i]) {
                return false;
            }
        }
        return true;
    }

    dfs(0, new Set());

    return answer.size;
}