[Programmers] 72411 메뉴 개발

Lee Jooam·2022년 4월 25일

코테에서 살아남기

출처: 프로그래머스 코딩테스트 연습

코딩 테스트는 지문을 해석하는 능력도 중요한 것 같습니다.

자신이 구현해야 할 기능, 예외사항 등 올바른 알고리즘을 구현하는데 필요한 요소들이 모두 지문에 숨겨져 있습니다.

국어 비문학 문제를 보는 것 같지만 제품의 요구사항을 판단하는 능력이라고 생각하고 열심히 하는 중입니다.

요구 사항

문제가 요구하는 것은 다음과 같습니다.

주어진 String과 Number를 통해 조합을 생성
구한 조합을 지속적으로 저장하며 counting
누적된 정보에서 counting이 2인 이상인 조합 중 가장 최대치인 요소 찾기

주의 사항

결과를 추출할 때 오름차순으로 sort
주어진 String이 항상 오름차순으로 들어오는 게 아님

구현

function solution(orders, course) {
  function getCombination(combAnswer, menu, fixed, select, index) {
    if (select === 0) {
      combAnswer.push(fixed);
      return;
    }

    for (let i = index; i < menu.length; i++) {
      if (menu.length - i < select) break;
      getCombination(combAnswer, menu, [...fixed, menu[i]], select - 1, i + 1);
    }
  }

  const answer = [];
  const info = {};
  const resultInfo = {};

  for (let c of course) {
    resultInfo[c] = {
      menu: "",
      counter: 0,
    };
  }

  for (let menu of orders) {
    const combAnswer = [];

    for (let c of course) {
      getCombination(combAnswer, menu.split("").sort().join(""), [], c, 0);
    }

    for (let comb of combAnswer) {
      if (!info[comb.join("")]) info[comb.join("")] = 0;

      info[comb.join("")]++;
    }
  }

  for (let menu in info) {
    if (info[menu] < 2) continue;

    if (resultInfo[menu.length].counter < info[menu]) {
      resultInfo[menu.length].menu = menu;
      resultInfo[menu.length].counter = info[menu];
    } else if (resultInfo[menu.length].counter == info[menu]) {
      resultInfo[menu.length].menu += `,${menu}`;
    }
  }

  for (let result in resultInfo) {
    if (resultInfo[result].menu.length) {
      answer.push(...resultInfo[result].menu.split(","));
    }
  }

  return answer.sort();
}

const orders = ["XYZ", "XWY", "WXA"];
const course = [2, 3, 4];

solution(orders, course);

  function getCombination(combAnswer, menu, fixed, select, index) {
    if (select === 0) {
      combAnswer.push(fixed);
      return;
    }

    for (let i = index; i < menu.length; i++) {
      if (menu.length - i < select) break;
      getCombination(combAnswer, menu, [...fixed, menu[i]], select - 1, i + 1);
    }
  }

조합을 구하는 함수입니다. 순열, 조합 알고리즘 구현을 토대로 작성했습니다.

외부 스코프에 있는 combAnswer 참조를 인자로 받아 계속 값을 누적시킵니다.

  const answer = [];
  const info = {};
  const resultInfo = {};

  for (let c of course) {
    resultInfo[c] = {
      menu: "",
      counter: 0,
    };
  }

  for (let menu of orders) {
    const combAnswer = [];

    for (let c of course) {
      getCombination(combAnswer, menu.split("").sort().join(""), [], c, 0);
    }

    for (let comb of combAnswer) {
      if (!info[comb.join("")]) info[comb.join("")] = 0;

      info[comb.join("")]++;
    }
  }

orders마다 course로 들어온 수만큼 경우의 수를 구합니다. 그리고 생성된 조합을 info object에 맵핑하고 그 count를 기록했습니다.

resultInfo는 동일한 count를 가지는 경우의 수가 있을 수 있기 때문에 추후 결과값 처리를 위해 선언했습니다.

 for (let menu in info) {
    if (info[menu] < 2) continue;

    if (resultInfo[menu.length].counter < info[menu]) {
      resultInfo[menu.length].menu = menu;
      resultInfo[menu.length].counter = info[menu];
    } else if (resultInfo[menu.length].counter == info[menu]) {
      resultInfo[menu.length].menu += `,${menu}`;
    }
  }

  for (let result in resultInfo) {
    if (resultInfo[result].menu.length) {
      answer.push(...resultInfo[result].menu.split(","));
    }
  }

  return answer.sort();
}