[프로그래머스_Lv2 ] 메뉴 리뉴얼 ( by using JavaScript )

문제

https://programmers.co.kr/learn/courses/30/lessons/72411

코딩테스트 연습 - 메뉴 리뉴얼

 

How to Solve?

 

[1] 완전 탐색

 

최초에 문제를 접했을 때는 반복되는 조합을 찾아서 출력한다는 개념으로 이해를 하였다!

 

즉, 1번 예시의 풀이법은

 

[A,C], [C,D,E], [A,C,D,E], [B,C,F,G], [A,B,C,F,G], [A,C,D,E,H]

순으로 나열하여서 1- > N번까지 순회하면서 [A,C]와 같은 조합이 다른 조합 속에 존재하면 추가해주고 정렬을 하는 방식으로 문제를 풀었는데 1번째 테스트케이스만 통과하는 사실을 통해서 붙어 있는 경우만을 원하는 것이 아니라 떨어져있더라도  ( [A,C] = [A,B,C] ) 또는  순서가 바뀌어 있더라도 ( [ A,C ] = [C,A] ) 문제가 없다는 것을 알고 "조합"을 원하는 문제 라는 것을 알 수 있었다.

function solution(orders, course) {
  const answer = [];
  orders.sort((a, b) => a.length - b.length);

  for (let i = 0; i < orders.length; i++) {
    for (let j = i + 1; j < orders.length; j++) {
      if (orders[j].includes(orders[i])) {
        answer.push(orders[i]);
        break;
      }
    }
  }

  let result = answer.filter((each) => course.includes(each.length));

  return result.sort();
}

 

[2] 조합 + 완전탐색

조합은 순서와 상관없는 경우의 수  즉, 순서가 다른 것은 같은 것으로 판단을 한다.



그리하여, 위에서 얻었던 생각을 바탕으로 순서가 다른 경우를 같게 판단하는 조합을 사용하면! 어떤 리뉴얼이 가장 많이 채택 됬는지 구현이 가능해진다

 

function getCombinations(arr, n) {
  const results = [];
  if (n === 1) return arr.map((e) => [e]);
  arr.forEach((e, idx, origin) => {
    const rest = origin.slice(idx + 1);
    const combinations = getCombinations(rest, n - 1);
    const attached = combinations.map((combination) => [e, ...combination]);
    results.push(...attached);
  });
  return results;
}

function solution(orders, course) {
  const answer = [];
  const comboArr = [];
  let map = {};
  orders = orders.map((e) => e.split("").sort());

  // 원하는 길이 만큼의, 조합을 얻기 위한 루프
  for (let i = 0; i < orders.length; i++) {
    for (let j = 0; j < course.length; j++) {
      comboArr.push(...getCombinations(orders[i], course[j]));
    }
  }
 
 // 조합을 정리
  comboArr.forEach((e) => {
    let joined = e.join("");
    map[joined] = (map[joined] || 0) + 1;
  });

// 정리된 조합을 배열로 전환
  let countArr = Object.entries(map);

  for (let i in course) {
    let tmpArr = countArr.filter((e) => e[0].length === course[i] && e[1] > 1);
    let max = Math.max(...tmpArr.map((e) => e[1]));
    tmpArr.forEach((e) => {
      if (e[1] === max) {
        answer.push(e[0]);
      }
    });
  }
  return answer.sort();
}