작성일 : 2024.11.08

불량 사용자 확인 문제

문제 설명

이벤트 응모자들 중 불량 사용자를 찾아내는 문제입니다. 불량 사용자 ID는 일부가 '*'로 가려져 있으며, 이에 매칭되는 실제 사용자 ID의 모든 조합을 찾아야 합니다.

예시

응모자 ID: ["frodo", "fradi", "crodo", "abc123", "frodoc"]
불량 사용자: ["fr*d*", "abc1**"]

가능한 제재 ID 조합:
1. ["frodo", "abc123"]
2. ["fradi", "abc123"]

제한 조건

1. user_id 배열

   • 크기: 1 ≤ 크기 ≤ 8
   • ID 길이: 1 ≤ 길이 ≤ 8
   • 구성: 알파벳 소문자, 숫자
   • 중복 없음

2. banned_id 배열

   • 크기: 1 ≤ 크기 ≤ user_id 배열 크기
   • 구성: 알파벳 소문자, 숫자, '*'
   • '*' 문자 최소 1개 포함

해결 코드

function solution(user_id, banned_id) {
  let answer = new Set();

  const matched = (user_id, banned_id) => {
    if (user_id.length != banned_id.length) return false;
    for (let chIndex = 0; chIndex < user_id.length; chIndex++) {
      if (banned_id[chIndex] != "*" && banned_id[chIndex] != user_id[chIndex]) {
        return false;
      }
    }
    return true;
  };

  const dfs = (level, selected) => {
    if (level == banned_id.length) {
      answer.add([...selected].sort().join(","));
      return;
    }
    for (let idIndex = 0; idIndex < user_id.length; idIndex++) {
      if (
        !selected.has(idIndex) &&
        matched(user_id[idIndex], banned_id[level])
      ) {
        selected.add(idIndex);
        dfs(level + 1, selected);
        selected.delete(idIndex);
      }
    }
  };

  dfs(0, new Set());
  return answer.size;
}

알고리즘 설명

1. ID 매칭 검사 (matched 함수)

const matched = (user_id, banned_id) => {
  // 길이가 다르면 매칭 실패
  if (user_id.length != banned_id.length) return false;

  // 문자별 비교
  for (let chIndex = 0; chIndex < user_id.length; chIndex++) {
    // '*'가 아니면서 문자가 다르면 매칭 실패
    if (banned_id[chIndex] != "*" && banned_id[chIndex] != user_id[chIndex]) {
      return false;
    }
  }
  return true;
};

2. DFS를 통한 조합 탐색

const dfs = (level, selected) => {
  // 모든 불량 사용자 매칭 완료
  if (level == banned_id.length) {
    answer.add([...selected].sort().join(","));
    return;
  }

  // 각 사용자 ID에 대해 매칭 시도
  for (let idIndex = 0; idIndex < user_id.length; idIndex++) {
    if (!selected.has(idIndex) && matched(user_id[idIndex], banned_id[level])) {
      selected.add(idIndex);
      dfs(level + 1, selected);
      selected.delete(idIndex);
    }
  }
};

주요 메서드 설명

1. Set 객체 활용

let answer = new Set(); // 중복 제거를 위한 Set
selected.add(idIndex); // 선택된 ID 추가
selected.delete(idIndex); // 선택 해제

2. 배열 메서드

[...selected].sort(); // Set을 배열로 변환 후 정렬
array.join(","); // 배열을 문자열로 변환

시간 복잡도

• O(n^m): n은 user_id의 수, m은 banned_id의 수

공간 복잡도

• O(m): m은 banned_id의 수 (Set 객체 사용)

문제 해결 포인트

1. 문자열 패턴 매칭
2. DFS를 통한 모든 가능한 조합 탐색
3. Set을 활용한 중복 조합 제거
4. 백트래킹을 통한 효율적인 탐색