[프로그래머스 lev3/JS] 불량 사용자

문제 출처

프로그래머스 lev3 - 불량 사용자

나의 풀이

1차 시도 (63.6/100)

(1) 각 index마다 불량 사용자 해당 목록을 찾고,
(2) 각 index마다 불량 사용자들을 조합해서 찾는다.

• 조합 아이디어를 가져와서 index = 0부터 시작해서 끝 지점에 도달했을 때 답을 찾는 방식을 사용해서 조합을 찾는다.

tray.sort()과 [...tray].sort()가 다르다.

• tray를 답으로 넣을 때 tray.slice()로 하는 것과 비슷한 개념인 듯한데, 이번 경우는 아예 로그로 찍히는 것부터가 다르므로 아직 뭔지 모르겠다..

function solution(user_id, banned_id) {
  const list = {}
  let answer = new Set()
  
  // (1)
  banned_id.map((b, idx) => {
    const stars = b.split("").filter(_ => _ === "*").length
    user_id.map(u => {
      const rest = u.split("").filter((_,i) => u[i] === b[i]).length
      if(u.length == stars + rest){
        // console.log(idx, u)
        if(list[idx]) list[idx].push(u)
        else if(!list[idx]) list[idx] = [u]
      }
    })
  })
  // console.log(list)
  
  // (2)
  function select(tray, start){
    if(start === banned_id.length) {
      // console.log(tray.sort()) trat.sort()가 아니라 [...tray].sort()로 로그를 찍어봐야 제대로 나온다. 
      answer.add([...tray].sort().slice().join("/"))
      return
    } 

    for(let i=0; i<list[start].length; i++){
      if(!tray.includes(list[start][i])){
        tray.push(list[start][i])
        select(tray, start + 1)
        tray.pop()
      }
    }
  }
  select([], 0)
  return answer.size
}

console.log(
  solution(
    ["frodo", "fradi", "crodo", "abc123", "frodoc"], 
    ["fr*d*", "abc1**"])
);
console.log(
  solution(
    ["frodo", "fradi", "crodo", "abc123", "frodoc"], 
    ["*rodo", "*rodo", "******"])
)
console.log(
  solution(
    ["frodo", "fradi", "crodo", "abc123", "frodoc"], 
    ["fr*d*", "*rodo", "******", "******"])
)

다른 풀이

(1) banned_id의 index 마다의 불량 사용자 목록을 찾는다.
(2) index 0부터 시작해서 끝 지점에 도달하면 답을 찾는 식으로 접근해서 불량 사용자 목록 조합을 찾는다(중복을 피하기 위해 set 생성자 함수를 사용한다)

const solution = (user_id, banned_id) => {
  const set = new Set();
  // (1)
  const banIds = banned_id.map((bid) =>
      user_id.filter((uid) => {
          if (uid.length !== bid.length) return false;

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

          return true;
      })
  );

  // (2)
  const DFS = (arr = [], idx = 0) => {
      if (idx === banned_id.length) {
          set.add(arr.sort().join(""));
          return;
      }

      for (const bid of banIds[idx]) {
          if (arr.includes(bid)) continue;
          else DFS([...arr, bid], idx + 1);
      }
  };

  DFS();

  return set.size;
};

다른 풀이 2

RegExp.prototype.exec() : 주어진 문자열에서 일치 탐색을 수행한 결과를 배열 또는 null로 반환한다.

const isUsed = {}
const usedSets = new Set();
const current = [];

function solution(user_id, banned_id, bannedIdx = 0) {
    const bannedLen = banned_id.length;
    if (bannedIdx === bannedLen) {
        const sorted = current.slice().sort().toString();
        if (usedSets.has(sorted)) {
            return 0;
        }

        usedSets.add(sorted);
        return 1;
    }

    const regex = new RegExp(banned_id[bannedIdx].replace(/\*/g, '.'));
    const matches = user_id.filter(user => {
        const result = regex.exec(user);
        return result && result[0].length === user.length;
    });

    let ret = 0;
    for (const user of matches) {
        if (!isUsed[user]) {
            isUsed[user] = true;
            current[bannedIdx] = user;
            ret += solution(user_id, banned_id, bannedIdx + 1);
            isUsed[user] = false;
        }
    }

    return ret;
}