[프로그래머스] 카카오 - 불량 사용자

문제

2019 카카오 개발자 겨울 인턴십 - 불량 사용자

https://school.programmers.co.kr/learn/courses/30/lessons/64064

 

 

풀이

설명

제재 아이디 목록을 만들 수 있는 경우의 수가 몇 개인지 구하는 문제입니다.

 

백트래킹을 이용해 해결할 수 있습니다.

 

가능한 모든 사용자 아이디 조합을 시도해야 합니다.

현재 아이디가 매칭되면 재귀호출을 통해 다음 매칭으로 넘어갑니다. 불가능하면 이전 단계로 돌아갑니다.

 

예시 코드

function solution(user_id, banned_id) {
  const bannedSet = new Set();
  const selected = [];

  dfs(0);

  return bannedSet.size;

  function dfs(depth) {
    if (depth === banned_id.length) {
      bannedSet.add([...selected].sort().toString());
      return;
    }

    for (let i = 0; i < user_id.length; i++) {
      if (selected.includes(user_id[i])) continue;
      if (!checkMatch(user_id[i], banned_id[depth])) continue;

      selected.push(user_id[i]);
      dfs(depth + 1);
      selected.pop();
    }
  }

  function checkMatch(user, ban) {
    if (user.length !== ban.length) return false;
    for (let i = 0; i < user.length; i++) {
      if (ban[i] !== "*" && user[i] !== ban[i]) return false;
    }

    return true;
  }
}