[Level2] 스킬트리, 메뉴 리뉴얼

in 코딩테스트 on 프로그래머스




스킬트리

프로그래머스

나의 풀이

function solution(skill, skill_trees) {
  let skillArr = skill.split("");
  let str = `[^${skillArr[0]}`;
  for (let i = 1; i < skillArr.length; i++) {
    str += `||^${skillArr[i]}`;
  }
  str += "]";
  for (let i = 0; i < skill_trees.length; i++) {
    skill_trees[i] = skill_trees[i].replace(new RegExp(str, "g"), "");
  }
  console.log(skill_trees);

  for (let i = 0; i < skill_trees.length; i++) {
    for (let j = 0; j < skillArr.length; j++) {
      skill_trees[i] = skill_trees[i].replace(
        new RegExp(skillArr[j], "g"),
        `${j + 1}`
      );
    }
  }

  const check = (num) => {
    let max = num[num.length - 1];
    for (let i = 1; i < max; i++) {
      if (!num.includes(`${i}`)) {
        return false;
      }
    }
    return true;
  };

  let cnt = 0;

  for (let i = 0; i < skill_trees.length; i++) {
    if (
      skill_trees[i] == skill_trees[i].split("").sort().join("") &&
      check(skill_trees[i])
    ) {
      cnt++;
    }
  }
  return cnt;
}


  1. 정규식 사용해서 필수 스킬 아닌 것 없앰
  2. 정규식 사용해서 스킬 트리 문자를 숫자로 변경
  3. 해당 숫자의 정렬값과 기존 수가 다르면 탈락
  4. 마지막 숫자 전의 숫자들이 없으면 탈락


내가 생각해도 너무 더럽고 복잡했다…!
다만 정규식에 변수 넣고 싶을 때 new RegExp() 사용해서 변수가 포함된 템플릿 문자열을 넣어도 된다는 사실을 알았다.

best 풀이

function solution(skill, skill_trees) {
    var answer = 0;
    var regex = new RegExp(`[^${skill}]`, 'g');

    return skill_trees
        .map((x) => x.replace(regex, ''))
        .filter((x) => {
            return skill.indexOf(x) === 0 || x === "";
        })
        .length
}

BCD가 아닌 것을 찾는게 나는 [^B^C^D] 로 했는데 [^BCD]도 동작이 같다..ㅠ
indexOf로 0이면 추가하는거 대박이다.
이걸 하면 가운데문자가 없다면 찾지 못하고, 앞에 문자가 없으면 0이 아니니 바로 찾아진다.



메뉴 리뉴얼

프로그래머스 

function solution(orders, course) {
  function getCombination(arr, selectNum) {
    let answer = [];
    if (selectNum === 1) return arr.map(keysue => [keysue]);

    arr.forEach((arrkeysue, index, origin) => {
      let rest = origin.slice(index + 1);
      let combination = getCombination(rest, selectNum - 1);
      let attach = combination.map(comkeysue => [arrkeysue, ...comkeysue]);
      answer.push(...attach);
    });

    return answer;
  }

  function getMaxMenu(menu) {
    let obj = {};
    let keys;
    let result = [];
    let max = -Infinity;
    for (let i = 0; i < menu.length; i++) {
      keys = menu[i].join('');
      if (!obj[`${keys}`]) {
        obj[`${keys}`] = 1;
      } else {
        obj[`${keys}`] = +obj[`${keys}`] + 1;
      }
    }
    for (let i in obj) {
      if (obj[i] > max) {
        max = obj[i];
        result = [];
        result.push(i);
      } else if (obj[i] == max) {
        result.push(i);
      }
    }
    return max === 1 ? false : result;
  }

  let combination;
  let answer = [];
  let maxMenu;

  for (let i = 0; i < course.length; i++) {
    combination = [];
    for (let j = 0; j < orders.length; j++) {
      combination.push(
        ...getCombination(orders[j].split(''), course[i]).map(val => {
          let temp = val.sort();
          return temp;
        })
      );
    }
    maxMenu = getMaxMenu(combination);
    if (maxMenu) {
      answer.push(...maxMenu);
    }
  }

  return answer.sort();
}

console.log(solution(['XYZ', 'XWY', 'WXA'], [2, 3, 4]));


  1. 조합 구하기
  2. 조합된 문자열 오름차순 정렬하기
  3. 가장 많이 나온 메뉴 고르기
  4. 최종 문자열 오름차순 정렬하기


우선 효율성이 좋진 않은 것 같지만, 나 스스로 푼 것에 만족을 느끼자..!!!
근데 베스트 풀이들도 다 같은 과정으로 풀어서, 이 문제는 어쩔수없이 효율성이 엄청 좋을 수는 없을 것같다.
(모든 경우의 수를 다 따져야하니까?)