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

사용 언어 : javascript
해결 날짜 : 2022-12-15
해결 방법 :
- dfs를 활용해 문제 해결
  - 방문 여부를 저장할 visited 배열 생성
  - 정규 표현식으로 id를 비교하기 위해 banned_id 속의 *을 .로 변경(정규 표헌식에서 .은 모든 글자 1글자)
  - banned_id의 index, 현재까지 저장된 불량 사용자 ids를 인자로 받는 dfs
    - index가 banned_id의 길이와 같을 경우 (모든 불량 사용자를 본 경우)
      - set에 ids를 추가하되, 중복 값을 제거하기 위해 정렬 후 문자열로 변환해 add()
      - dfs 종료
    - 그 외의 경우 user_id를 돌며
      - 현재 user를 방문하지 않았고, 현재 index의 불량 사용자와 일치할 경우
        
        백트래킹 수행
회고 :
- 처음에 배열의 크기와 원소의 길이가 8로 작길래 단순 완전 탐색 문자열 문제인줄 알았으나 아니었다.
- 다른 사람의 풀이를 보니, 순열로도 해결할 수 있는 것 같아 다음에 풀어봐야겠다.

코드

function solution(user_id, banned_id) {
  const visited = Array.from({ length: user_id.length }, () => false);
  const regex = banned_id.map((id) => new RegExp(`^${id.replaceAll('*', '.')}$`));
  const set = new Set();

  const dfs = (index = 0, ids = []) => {
    if (index === banned_id.length) {
      set.add(ids.sort().join(' '));
      return;
    }

    for (let i = 0; i < user_id.length; i++) {
      if (!visited[i] && user_id[i].match(regex[index])) {
        visited[i] = true;
        dfs(index + 1, [...ids, user_id[i]]);
        visited[i] = false;
      }
    }
  };

  dfs();

  return set.size;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges