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

문제링크

https://programmers.co.kr/learn/courses/30/lessons/64064?language=javascript#

풀이

일치하는 패턴의 개수를 찾는 문제이기 때문에 dfs 방식으로 접근하였습니다. bfs알고리즘 구현에 앞서 "fro*o"를 "frodo"와 패턴을 맞추는 함수 인 $match()$를 구현하였습니다.

function match(id, pattern) {
  pattern = pattern.replace(/\*/g, ".");
  const regex = RegExp("\^(" + pattern + "\)$")
  return regex.test(id)
}

parameter로는 아이디값과 패턴을 받아옵니다. 패턴에 쓰여진 *은 정규식에서 . 과 같은 의미로 사용됩니다. 따라서 replace를 통해 *값을 모두 . 으로 바꾸어 주었습니다. (replace() 원래 최초값 하나에만 적용이 되지만 replace(/\*/g , ".") 처럼 정규식을 사용하면 모든 *을 . 으로 변경할 수 있습니다.)

이 상태에서 패턴매칭을 하게되면 "frodoc"을 "frod*"와 같은 자리수가 안맞는 패턴에 true를 반환할 것입니다. 따라서 pattern의 앞뒤에 각각 \^와, $을 넣어 앞자리와 끝자리임을 표기시켜줍니다. ( \^표시는 첫번째 자리임을 $표시는 끝자리임을 나타냅니다. )

이 regExp.test(param)라는 메소드는 parameter로 주어진 값이 regExp의 패턴과 일치하는 확인하는 함수 입니다.

match() 함수의 구현은 console.log를 통하여 잘 작동합을 확인하였습니다. 이제 다음은 dfs알고리즘을 구현하는 것입니다.

dfs알고리즘은 주로 스택 또는 재귀함수로 많이 구현합니다. 제가 생각하는 bfs함수의 대략적인 구조는 이러합니다.

function bfs(arr){
  //조건에 해당하는 경우 -> 주로 depth 확인
  if(arr.length==0){ 
  	answer+=1
    return 
  }
  else {
    for(var i=0; i<arr.length; i++){
      if(arr[i]=="조건") bfs([...arr.slice(0,i),...arr.slice(i+1)])
    }
    return 
  }
}

이 문제에서는 매번 재귀함수에 들어갈때 user_id와 banned_id를 가지고 가야합니다. (그래야 모든 경우의 수를 따질 수 있습니다.) 따라서 param에 패턴이 일치하는 user_id와 패턴을 하나씩 뺀 상태로 dfs에 다시 넣었습니다. 단순 객체 복사를 하게되면 재귀함수에서 기존 변수를 건드려 이상한 값이 되니 slice를 통해 shallow 이상의 카피를 해야합니다.

function solution(user_id, banned_id) {
  answer = 0

  dfs(user_id.slice(), banned_id.slice());
  return answer;
}
var answer

function dfs(remain_users, banned_id, ban) {
  if (banned_id.length == 0) {
    answer+=1
    return 
  }
  else {
    for (var idx = 0; idx < remain_users.length; idx++) {
      if (match(remain_users[idx], banned_id[0])) {
        dfs([...remain_users.slice(0, idx), ...remain_users.slice(idx + 1)],
          banned_id.slice(1)
        )
      }
    }
    return 0
  }
}

function match(id, pattern) {
  pattern = pattern.replace(/\*/g, ".");
  const regex = RegExp("\^(" + pattern + "\)$")
  // console.log(id, pattern,regex.test(id)) 
  return regex.test(id)
}

하지만 이렇게 만든 풀이는 테스트 케이스 1만 맞고 2,3은 틀렸습니다. 왜냐하면 테스트 케이스 2의 banned_id 예시를 보게되면 ["*rodo", "*rodo", "******"] 으로 되어있습니다. 구현한 함수를 통해 결과값을 나타내면 ["frodo", "crodo", ...] 과 ["crodo","frodo", ...] 이 두개의 배열을 각각 다른 값으로 취급하는데 문제 조건에서는 같은 값으로 취급합니다.

따라서 배열을 모두 모아서 정렬하고 중복값을 제거해주어야 합니다. 먼저 dfs함수 param에 arr값을 전달하여 불량사용자 아이디를 모으고 마지막에 중복제거를 하려합니다.

중복값 제거를 하기 위해서는 arr을 각각 정렬한 후 중복제거 method를 이용해야합니다. arr은 [["frodo","crodo"],["crodo","frodo"],[...]]와 같이 2중배열의 형태를 띄고 있기 때문에 arr.map(item=>item.sort())로 각각을 정렬하고 중복제거 함수에 넣었습니다.

중복제거 함수
Array.from(new Set(arr))

이 함수를 통해 중복을 제거한 배열의 length가 answer이 될 것입니다.

[성공 코드]

function solution(user_id, banned_id) {
  answer = 0

  dfs(user_id.slice(), banned_id.slice(), []);
  answer = Array.from(new Set(arr.map(i => i.sort().join()))).length
  return answer;
}
var answer
var arr = []

function dfs(remain_users, banned_id, ban) {
  if (banned_id.length == 0) {
    arr.push(ban)
    return 1
  }
  else {
    for (var idx = 0; idx < remain_users.length; idx++) {
      if (match(remain_users[idx], banned_id[0])) {
        dfs([...remain_users.slice(0, idx), ...remain_users.slice(idx + 1)],
          banned_id.slice(1),
          [...ban, remain_users[idx]]
        )
      }
    }
    return 0
  }
}

function match(id, pattern) {
  pattern = pattern.replace(/\*/g, ".");
  const regex = RegExp("\^(" + pattern + "\)$")
  // console.log(id, pattern,regex.test(id)) 
  return regex.test(id)
}