[프로그래머스] 불량 사용자 / JavaScript / Level 3

🚩문제 주소

📄풀이

순열

const Permutation = (arr, num) => {
  const result = [];
  if (num === 1) return arr.map((v) => [v]);

  arr.forEach((select, i, origin) => {
    const remainder = [...origin.slice(0, i), ...origin.slice(i + 1)];
    const permutation = Permutation(remainder, num - 1);
    const combine = permutation.map((v) => [select, ...v]);
    result.push(...combine);
  });

  return result;
};

순열 배열을 만들어주는 함수입니다.

const check = (uid, bid) => {
  uid = uid.sort((a, b) => a.length - b.length);
  bid = bid.sort((a, b) => a.length - b.length);

  for (let i = 0; i < uid.length; i++) {
    if (uid[i].length !== bid[i].length) return false;

    for (let j = 0; j < uid[i].length; j++) {
      if (bid[i][j] === "*") continue;
      if (uid[i][j] !== bid[i][j]) return false;
    }
  }
  return true;
};

인자로 받은 유저아이디배열과 불량사용자아이디배열을 아이디의 길이 기준으로 정렬해준 후, 비교합니다.
두 아이디의 길이가 같지 않다면 false 반환, 두 아이디의 각 자리의 알파벳이 같지 않다면 false를 반환해주고, 조건을 전부 만족한다면 true를 반환합니다.

const permutation = Permutation(user_id, banned_id.length);
const checkArr = permutation.filter((v) => check(v, banned_id));
const set = new Set();
checkArr.forEach((v) => set.add(v.sort().join("")));

순열을 사용하여 불량사용자아이디 갯수만큼 유저아이디 경우의 수를 모두 만들어 줍니다.

check 함수를 통해 조건을 만족하는 아이디들을 가진 배열을 만듭니다.

아이디들을 정렬한 뒤 join하여 문자열로 만들어준 후, set을 활용하여 중복을 제거합니다.

set의 size을 반환하면 정답이 나옵니다.

👨‍💻코드

const Permutation = (arr, num) => {
  // 시간복잡도 O(n!)
  const result = [];
  if (num === 1) return arr.map((v) => [v]);

  arr.forEach((select, i, origin) => {
    const remainder = [...origin.slice(0, i), ...origin.slice(i + 1)];
    const permutation = Permutation(remainder, num - 1);
    const combine = permutation.map((v) => [select, ...v]);
    result.push(...combine);
  });

  return result;
};

const check = (uid, bid) => {
  // 시간복잡도 O(n^2)
  uid = uid.sort((a, b) => a.length - b.length);
  bid = bid.sort((a, b) => a.length - b.length);

  for (let i = 0; i < uid.length; i++) {
    if (uid[i].length !== bid[i].length) return false;

    for (let j = 0; j < uid[i].length; j++) {
      if (bid[i][j] === "*") continue;
      if (uid[i][j] !== bid[i][j]) return false;
    }
  }
  return true;
};

function solution(user_id, banned_id) {
  // 시간복잡도 O(n!)
  const permutation = Permutation(user_id, banned_id.length);
  const checkArr = permutation.filter((v) => check(v, banned_id));
  const set = new Set();
  checkArr.forEach((v) => set.add(v.sort().join("")));

  return set.size;
}