문제 링크

프로그래머스 문제

풀이

다소 복잡한 예외처리와 DFS를 통해서 효율적으로 문제를 해결해야 하는 문제 입니다.
보자마자는 아니지만 예상할 수 있는 가장 시간초과가 발생할 것이라 예상되는 테스트 케이스는 다음과 같습니다.

userID :
["12345678", "23456781", "34567812", "45678123", "56781234", "67812345", "78123456", "81234567"];

bannedID : 
["********", "********", "********", "********", "********", "********", "********", "********"]

예상 결과 : 
1

이때 , 발생하는 문제는 첫 bannedID의 모든 경우의 수를 구한다면, 8 ^ 8(16,777,216) 이 만들어져, 심각한 시간초과가 발생하게 될것이라 생각할 수 있었습니다.

따라서 가능한 bannedList를 만든 후 그 속에서 중복된 값을 모두 제거해가며 List를 만들려고 생각했습니다.

1. 이미 속한 userID를 제거 해야한다. -> DFS 를 돌면서 그 해당 단계에서 중복된경우 넘기고 다음것을 확인
2. 만들어진 List자체가 중복인경우 -> 이때 마지막 생성할 수 있는 모든 list를 찾아서 set 함수를 이용해 중복을 제거 합니다.

코드

function solution(user_id, banned_id) {
    var answer = [];
    
    const possible_banned_list = []
    // [[ ... , ... , ] , [ .... , ... , ...] , [ .... , ...]]
    
    for(let i=0; i< banned_id.length; i++){
        possible_banned_list.push([])
        for(let j=0; j< user_id.length; j++){
            if(isBannedId(user_id[j] , banned_id[i] )){
                possible_banned_list[i].push(user_id[j])
            }
        }
    }
    // possible_banned_list는 0번째의 bannedID를 통해 생성할 수 있는 가능한 userID의 목록입니다. 
  
    const dfs = (curId , index , curArray) => {
        // 종료 조건
        if(index === banned_id.length -1){
            answer.push(curArray.sort().join(",")) // 마지막 종료 조건에 도달했을때, answer 들 중에서 중복을 제거 하기 위해서 curArray를 정렬하여 순서를 맞추었구, join을 통해 2중 배열에서의 탐색이 아닌 하나의 문자열로 통일시켰습니다. 
            return;
        }
        
        // 다음 조건
        for(let i=0; i < possible_banned_list[index+1].length; i++){
            if(!curArray.includes(possible_banned_list[index+1][i])){ // 포함하고 있지 않다면
                dfs(possible_banned_list[index+1][i] , index+1 , [... curArray , possible_banned_list[index+1][i] ])
            }
        }
    }
    
    for(let i=0; i < possible_banned_list[0].length; i++){
        dfs(possible_banned_list[0][i] , 0 , [possible_banned_list[0][i]])
    }
    
    return [...new Set(answer)].length; // 마지막 answer의 중복이 제거된 배열의 길이를 통해 List의 길이를 셀수 있습니다. 
}

function isBannedId (userId, bannedId) {
    
    if(userId.length !== bannedId.length){
        return false;
    }
    for(let i=0; i< userId.length; i++){
        if(userId[i] !== bannedId[i] && bannedId[i] !== "*"){
            return false
        }
    }
    
    return true
    
}