불량 사용자

문제 접근

복잡해 보이지만 단순한 순열 조합 문제입니다.

1. 각각의 banned_id가 가질 수 있는 경우의 수 구하기
2. 각각의 경우의 수를 이용해 조합을 계산
3. 조합의 개수 = 정답

예를 들면 "fr*d*"는 ["frodo", "fradi"], "abc1**"는 ["abc123"]를 가질 수 있으므로 조합은 ["frodo","abc123"] , ["fradi","abc123"] 로 총 2가지 입니다.

이 때, dfs로 순열들을 구하고, 그 중 순서는 다르지만 값이 같은 배열들을 제거하기 위해, sort 와, string 변환 이후 set을 이용해 조합을 구했습니다.
(😅 더 좋은 방법이 분명 있을텐데..)

문제 풀이

시간의 압박을 느끼며 짜다보니, 이렇게 괴상한 코드가 만들어졌습니다 ㅎㅎ..

function solution(user_id, banned_id) {
  const bannedIdObj = banned_id.reduce((acc, banned, idx) => {
    user_id.forEach((user) => {
      if (user.length !== banned.length) {
        return
      } else {
        let isSame = true
        banned.split('').forEach((bannedChar, idx) => {
          if (bannedChar !== '*' && bannedChar !== user[idx]) {
            isSame = false
            return
          }
        })
        if (isSame) {
          if (acc[idx]) acc[idx].push(user)
          else acc[idx] = [user]
        }
      }
    })
    return acc
  }, {})

  const bannedIdArr = Object.entries(bannedIdObj).map((e) => e[1])
  const resultArr = []
  const dfs = (history, level) => {
    if (level === banned_id.length) {
      resultArr.push(history)
      return
    } else {
      bannedIdArr[level].forEach((bannedId) => {
        const newHistory = [...history]
        if (!newHistory.includes(bannedId)) {
          newHistory.push(bannedId)
          dfs(newHistory, level + 1)
        }
      })
    }
  }

  dfs([], 0)
  const resultArrSorted = new Set(
    resultArr
      .map((e) => e.sort())
      .map((e) => e.join('')),
  )

  const ans = [...resultArrSorted]
  return ans.length
}

개선할 점

개선할 점은 다음과 같습니다.

1. fr*d*와 frodo를 비교할 때, 정규표현식(test) 사용가능

수정한 코드

function solution(user_id: string[], banned_id: string[]) {
  const N = banned_id.length
  const answer = []
  const bannedArr = banned_id.reduce((acc, banned) => {
    const bannedPeople = user_id.reduce((userAcc, user) => {
      if (user.length === banned.length) {
        const regExp = new RegExp(banned.replace(/\*/g, '.'))
        if (regExp.test(user)) userAcc.push(user)
      }
      return userAcc
    }, [])
    acc.push(bannedPeople)
    return acc
  }, [])

  const dfs = (level, visited) => {
    if (level === N - 1) {
      answer.push(visited)
      return
    } else {
      bannedArr[level + 1].forEach((ban) => {
        if (!visited.includes(ban)) {
          const newVisited = [...visited]
          newVisited.push(ban)
          dfs(level + 1, newVisited)
        }
      })
    }
  }
  if (bannedArr.length >= 1) {
    bannedArr[0].forEach((ban) => {
      dfs(0, [ban])
    })
  }
  const set = new Set(answer.map((e) => JSON.stringify(e.sort())))
  return set.size
}