[프로그래머스] 메뉴 리뉴얼 - Lv. 2 / JavaScript

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

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

 

문제 설명

하나의 단품 메뉴는 A~Z까지의 알파벳으로 이루어져 있다.

단품 메뉴 조합이 ABC, BC와 같이 문자열로 되어 있는 문자열 배열과 만들고 싶은 코스 요리(단품 메뉴의 조합)의 단품 메뉴 개수 배열이 입력으로 주어진다.

단품 메뉴 주문 중 코스요리로 만들려면 손님들이 두 번 이상 그 조합을 시켜야 하고, 그 중에서 가장 많이 시킨 조합이어야 한다.

손님 번호                                                                   주문한 단품메뉴 조합

1번 손님	A, B, C, F, G
2번 손님	A, C
3번 손님	C, D, E
4번 손님	A, C, D, E
5번 손님	B, C, F, G
6번 손님	A, C, D, E, H

가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

코스 종류                            메뉴                    구성설명

요리 2개 코스	A, C	1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스	C, D, E	3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스	B, C, F, G	1번, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스	A, C, D, E	4번, 6번 손님으로부터 총 2번 주문됐습니다.

 

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

---

문제 해결 아이디어

 

주문한 단품 메뉴 조합에서 코스요리로 만들고 싶은 개수를 모두 조합으로 뽑는다. 그 후에 똑같은 조합이 뽑히면 cnt를 하나씩 늘리는 식으로 나올 수 있는 조합을 다 뽑고 메모해 둔다.

그리고 뽑힌 수로 정렬해서 2개 이상 가장 많이 뽑힌 조합을 정답 배열에 넣는다.

---

 

완성된 코드

처음부터 가능한 조합과 그 조합이 뽑힌 수를 조합: 수로 해서 객체로 넣었는데 그냥 배열로 넣었으면 굳이 이렇게 정렬을 위해 여러번 왔다갔다 안 했을 것 같기도 하다. 

다시 풀어 봐야겠다.

+ 다시 풀어보려니까 또 조합이 있는지 아닌지 for문 돌려서 한번 찾아봐야 되는 거라 이게 나을 것 같기도 하고...

function solution(orders, course) {
  var answer = [];
  let menu = [];
  let sortedMenu = [];
  let picks = "";
  let isSelected = Array(orders[0].length).fill(false);

  for (let i = 0; i < course.length; i++) {
    menu.push({});
  }

  // 가능한 코스메뉴 조합 뽑기
  const pick = (start, cnt, target, now) => {
    // 다뽑으면
    if (cnt === course[target]) {
      let temp = picks.split("").sort().join("");
      if (menu[target][temp]) menu[target][temp]++;
      else menu[target][temp] = 1;
      return;
    }

    for (let i = start; i < now.length; i++) {
      if (isSelected[i]) continue;
      picks += now[i];
      isSelected[i] = true;
      pick(i, cnt + 1, target, now);
      isSelected[i] = false;
      picks = picks.slice(0, picks.length - 1);
    }
  };

  for (let i = 0; i < orders.length; i++) {
    isSelected = Array(orders[i].length).fill(false);
    for (let j = 0; j < course.length; j++) {
      pick(0, 0, j, orders[i]);
    }
  }

  // 뽑힌 순서 대로 정렬. 객체 정렬을 위해 배열로 바꿔줌
  for (let i = 0; i < menu.length; i++) {
    let sortable = [];
    for (let course in menu[i]) {
      sortable.push([course, menu[i][course]]);
    }
    sortable.sort((a, b) => {
      return b[1] - a[1];
    });
    sortedMenu.push(sortable);
  }

  // 2 이상인 코스만 뽑으니까 최대를 2로 초기화하고 큰 게 있으면 바꿔줌 그 값이면 정답 아닌거는 break
  for (let i = 0; i < sortedMenu.length; i++) {
    let max = 2;
    for (let j = 0; j < sortedMenu[i].length; j++) {
      if (sortedMenu[i][j][1] >= max) {
        max = sortedMenu[i][j][1];
        answer.push(sortedMenu[i][j][0]);
      } else {
        break;
      }
    }
  }

  answer.sort();

  return answer;
}