불량 사용자 javascript

HyosikPark·2021년 3월 27일
0

알고리즘

목록 보기
68/72
function solution(user_id,banned_id) {
    const result = [];
    const numOfCase = [];
  
    banned_id.forEach((banned_name,idx) => {
        numOfCase[idx] = [];
        user_id.forEach(user_name => {
            if (banned_name.length !== user_name.length) return
            
            for (let i = 0; i < banned_name.length; i++) {
                if (banned_name[i] !== '*') {
                    if(banned_name[i] !== user_name[i]) return
                }
            }            
            
            numOfCase[idx].push(user_name);
        })
    })
    
    
    function recursive(i,arr) {
        if (numOfCase.length === i) return arr
        
        numOfCase[i].forEach((e) => {
            if(arr.includes(e)) return null;
            const copy = [...arr,e];
            const combi = recursive(i+1,copy);
            
            if (combi) {
                const str = combi.sort().join()
                if (!result.includes(str)) {
                    result.push(str);
                }
            }
        })
    }
    recursive(0,[])
    
    return result.length;
}

해설

    const result = [];
    const numOfCase = [];
  
    banned_id.forEach((banned_name,idx) => {
        numOfCase[idx] = [];
        user_id.forEach(user_name => {
            if (banned_name.length !== user_name.length) return
            
            for (let i = 0; i < banned_name.length; i++) {
                if (banned_name[i] !== '*') {
                    if(banned_name[i] !== user_name[i]) return
                }
            }            
            
            numOfCase[idx].push(user_name);
        })
    })

console.log(numOfCase) 
/* 
[
  [ 'frodo', 'fradi' ],
  [ 'frodo', 'crodo' ],
  [ 'abc123', 'frodoc' ],
  [ 'abc123', 'frodoc' ]
] */

ban당한 id가 될 수 있는 user_id들을 담은 2차원 배열을 만듭니다.
위 예시를 볼 때

["frodo", "fradi", "crodo", "abc123", "frodoc"]	
["fr*d*", "*rodo", "******", "******"]

ex) "fr*d*"일 경우 [ 'frodo', 'fradi' ] 가 가능.
ex) "*rodo"일 경우 [ 'frodo', 'crodo' ]가 가능.
ex) "******"일 경우 [ 'abc123', 'frodoc' ]가 가능.
ex) "******"일 경우 [ 'abc123', 'frodoc' ]가 가능.
function recursive(i,arr) {
        if (numOfCase.length === i) return arr
        
        numOfCase[i].forEach((e) => {
            if(arr.includes(e)) return null;
            const copy = [...arr,e];
            const combi = recursive(i+1,copy);
            
            if (combi) {
                const str = combi.sort().join()
                if (!result.includes(str)) {
                    result.push(str);
                }
                
            }
        })
    }
    recursive(0,[])
    
    return result.length;

가능한 조합을 찾는 재귀문으로 난이도가 있습니다.
유저 id를 숫자로 바꿔 생각해 보면
예를들어 [[1,2], [1,2], [3,4]] 일 때 각 배열에서 한 숫자씩 빼낼 때 가능한 조합은
[1,1,3], [1,1,4], [1,2,3], [1,2,4], [2,1,3], ...

하지만 위 문제에서는 같은 숫자(user_id)는 포함되면 안되며 순서가 달라도 같은 경우의 수로 취급되어야 합니다.

먼저 가능한 모든 조합을 계산하는 재귀문을 작성해 보도록 하겠습니다.

const numOfCase = [[1,2], [1,2], [3,4]];
const result = [];

function recursive(i, arr) {
  if (numOfCase.length === i) return arr
  
  numOfCase[i].forEach(e => {
    const copy = [...arr, e];
    const combi = recursive(i+1, copy);
    // combi가 undefined인 경우도 있습니다.
    if (combi) result.push(combi);
  })
}

recursive(0,[])

console.log(result);
/*
[
  [ 1, 1, 3 ],
  [ 1, 1, 4 ],
  [ 1, 2, 3 ],
  [ 1, 2, 4 ],
  [ 2, 1, 3 ],
  [ 2, 1, 4 ],
  [ 2, 2, 3 ],
  [ 2, 2, 4 ]
] */

하지만 여기서 중복된 값들의 배열은 포함되면 안됩니다. 따라서 조건을 추가합니다.

numOfCase[i].forEach(e => {
  // 여기에 조건을 추가합니다.
    if (arr.includes(e)) return null;
    const copy = [...arr, e];
  ...
  
  console.log(result)
  // [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 2, 1, 3 ], [ 2, 1, 4 ] ]

여기서 ([1,2,3][2,1,3]) ([1,2,4][2,1,4])는 중복되는 배열이므로 하나는 삭제해야 합니다. 하지만 객체나, 배열의 경우 같은 똑같이 생긴 배열이라도 다른 값으로 취급됩니다.
ex) const arr = [1];
console.log(arr == [1]) // false;
따라서 sort()로 정렬한 뒤 join()으로 문자열로 만들어 비교하여 판단해야합니다.

numOfCase[i].forEach((e) => {
            if(arr.includes(e)) return null;
            const copy = [...arr,e];
            const combi = recursive(i+1,copy);
            
            if (combi) {
              // 문자열로 만들어 포함되어 있지 않을 경우 추가
                const str = combi.sort().join()
                if (!result.includes(str)) {
                    result.push(str);
                }
            }
  
  console.log(result) // [ '1,2,3', '1,2,4' ]

모든 경우의 수는 result.length가 됩니다.

0개의 댓글