프로그래머스 - Lv.3 메뉴 리뉴얼 (백트래킹) node.js

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

 

해당 문제를 요약하면 다음과 같다. order 에는 문자열의 조합이 주어지고, course에는 만들고자 하는 조합의 크기가 주어진다.

여기서 문자열을 조합(combination)하여 course에 나타난 길이별로 가장 빈도가 높은 조합을 반환하는 문제다. (만약 빈도가 같은 조합이 여러 개라면 모두 출력한다.)

 

문제 풀이 방식

문자열을 course에 나오는 각 길이별로 조합하였을 때, 해당 빈도수를 담기 위해서는 객체를 활용하는 것이 효율적이므로, 이를 활용했다.

다만, '각 길이별 가장 높은 빈도의 문자열'을 추출해내는 것이 중요하므로, 길이별로 각각의 객체를 구현하는 것이 나중에 데이터를 처리하는 것에 효율적이라고 판단하였고 course에서 가장 높은 값을 길이로 하며 요소는 객체로 갖는 배열을 선언했다.

function solution(order, course) {
  const tables = Array.from(
    { length: Math.max(...course) + 1 },
    (el) => (el = {})
  );

 

이후 각 문자별 길이에 따른 조합(combination)을 구하기 위해 어떤 방식을 사용해야 할지 고민했다. 파이썬이었다면 내장 모듈인 combintaion을 활용해 구해냈겠지만, 자바스크립트 환경이다 보니 내가 알고있는 알고리즘 중에는 백트래킹이 가장 효율적이리라는 생각이 들었다. (order의 각 요소의 크기가 2이상 10이하 이기 때문)

백트래킹 알고리즘은 아래와 같다.

function getCombination(str, leng) {
  const arr = str.split("").sort(); // 문제 예제에서 'XWY'라는 기존 알파벳 순과 다른 경우 존재

  const combination = [];
  function combine(cur, start) {
    if (cur.length === leng) {
      combination.push(cur.join(""));
      return;
    }

    for (let i = start; i < arr.length; i++) {
      cur.push(arr[i]);
      combine(cur, i + 1);
      cur.pop();
    }
  }
  combine([], 0);
  return combination;
}

 

 

만약 문자열과, 내가 만들어내고자 하는 길이를 인자로 전달한다고 했을 때, 백트래킹을 통해 해당길이와 일치하는 모든 조합을 완성할 수 있다. 그리고 해당 알고리즘은 아래와 같은 과정을 거쳐 tables 내 각 길이에 맞는 객체로 값이 추가된다.

function solution(order, course) {
 // 중략
 
  order.forEach((el) => {
    course.forEach((leng) => {
      const combinations = getCombination(el, leng);
      combinations.forEach((com) => {
        tables[leng][com] = (tables[leng][com] || 0) + 1;
      });
    });
  });

 

다음으로 문제에서 요구하는 각 길이 별 최대 빈도를 가진 문자열 조합을 추출해내는 로직을 작성했다. 이때, 문제에서 요구하는 빈도는 최소 2이므로 객체에 저장되어 있는 value가 1인 경우는 필터링하는 과정을 거쳤다. 그리고 이때, 필터링한 이후 해당 조건을 만족하는 요소가 존재하지 않는다면 바로 빈배열을 리턴했다. (아래 리턴되는 munus는 결국 배열이기 때문에 같은 방식인 배열로 리턴함으로써 처리를 편하게 하기 위함이다.)

function getMenu(obj) {
  const entries = Object.entries(obj)
    .filter((el) => el[1] !== 1) // 빈도 1인 경우 제거
    .sort((a, b) => b[1] - a[1]); // 빈도 오름차순 정렬

  if (entries.length == 0) return [];

  const menus = [];
  const max = entries[0][1];
  for (let i = 0; i < entries.length; i++) {
    if (max == entries[i][1]) {
      menus.push(entries[i][0]);
    } else break;
  }
  return menus;
}

 

그리고 이 코드는 아래와 같이 처리되어, result 의 이차원으로 저장된 배열을 1차원으로 바꾸고 정렬한 뒤 답안을 리턴할 수 있도록 했다.

function solution(order, course) {
  // 테이블 선언 코드

  // getCombination 함수 호출 코드

  const result = [];
  tables.forEach((table) => {
    if (Object.values(table).length) result.push(getMenu(table));
  });

  return result.flat().sort();
}

 

전체 소스 코드

function solution(order, course) {
  const tables = Array.from(
    { length: Math.max(...course) + 1 },
    (el) => (el = {})
  );

  order.forEach((el) => {
    course.forEach((leng) => {
      const combinations = getCombination(el, leng);
      combinations.forEach((com) => {
        tables[leng][com] = (tables[leng][com] || 0) + 1;
      });
    });
  });

  const result = [];
  tables.forEach((table) => {
    if (Object.values(table).length) result.push(getMenu(table));
  });

  return result.flat().sort();
}

function getCombination(str, leng) {
  const arr = str.split("").sort();

  const combination = [];
  function combine(cur, start) {
    if (cur.length === leng) {
      combination.push(cur.join(""));
      return;
    }

    for (let i = start; i < arr.length; i++) {
      cur.push(arr[i]);
      combine(cur, i + 1);
      cur.pop();
    }
  }
  combine([], 0);
  return combination;
}

function getMenu(obj) {
  const entries = Object.entries(obj)
    .filter((el) => el[1] !== 1)
    .sort((a, b) => b[1] - a[1]);

  if (entries.length == 0) return [];

  const menus = [];
  const max = entries[0][1];
  for (let i = 0; i < entries.length; i++) {
    if (max == entries[i][1]) {
      menus.push(entries[i][0]);
    } else break;
  }
  return menus;
}

console.log(
  solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2, 3, 4])
);