[프로그래머스] level.2 메뉴 리뉴얼

 

프로그래머스

---

나의 풀이 

처음에는 그렇게 어려운 문제가 아니라고 생각했습니다. 

그래서 문제설계를 아래와 같이 하였습니다.

1. sort : 원소의 길이 오름차순으로 정렬
2. for문으로 순회하면서 0번째 원소부터 나를 포함하고 있는 인원체크
3. 주문 횟수 내림차순으로 정렬
4. return

하지만 이렇게 하면 완전 문제를 잘 못 이해하고 있는 것 입니다.  

 

 

예제 1번처럼 `orders`가 이렇게 주어졌을 때

["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]

 

이렇게 원소길이를 기준으로 오른차순으로 정렬 한 뒤에 AC와 CDE 비교해서 같은거 찾고 AC와 ACDE비교해서 같은것 찾고

orders = ["AC","CDE", "ACDE", "BCFG", "ABCFG", "ACDEH"]

 

 

이런식으로 하는게 아닙니다.

 

 

문제에 직접적으로 나와있지는 않지만 글을 잘 읽어보면 "가장 많이 함께 주문된 단품메뉴 조합에 따라 `스카피`가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다. "

 

이 말은 함께 주문된 단품메뉴 조합의 개수가 같다면 가장 많이 주문된 조합을 고르라는 뜻 입니다. 

 

예를들어 문제의 두 번째 예제를 보시면 아래와 같습니다.

orders = ["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]

여기에서 요리 2개 코스는 `"AB"`, `"AD"`, `"AC"`, `"CD"`, `"XY"`, `"XZ"`, `"YZ"` 가 있습니다.  

하지만 여기서 제일 많이 주문된 것은 세 번 주문된 `"AD"`, `"CD"` 입니다.

 

 

이 문제를 풀기위해서는 요리 n개 코스의 모든 조합을 구한뒤 course에 맞는 조합중에 가장 많이 주문된 조합을 고르면 됩니다.

정리해보면 아래와 같은 순서로 풀면 쉽습니다.

 

 

1. orders를 가지고 나올 수 있는 모든 주문의 조합을 만듭니다. (최소 단품 메뉴 2개 이상)

문제 예제 1의 orders 모든 조합

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

 

2.  각 조합을 카운트 합니다.

{
  AB: 1,
  AC: 4,
  AF: 1,
  AG: 1,
  BC: 2,
  BF: 2,
  BG: 2,
  CF: 2,
  CG: 2,
  FG: 2,
  ABC: 1,
  ABF: 1,
  ABG: 1,
  ACF: 1,
  ACG: 1,
  AFG: 1,
  BCF: 2,
  BCG: 2,
  BFG: 2,
  CFG: 2,
  ABCF: 1,
  ABCG: 1,
  ABFG: 1,
  ACFG: 1,
  BCFG: 2,
  CD: 3,
  CE: 3,
  DE: 3,
  CDE: 3,
  AD: 2,
  AE: 2,
  ACD: 2,
  ACE: 2,
  ADE: 2,
  ACDE: 2,
  AH: 1,
  CH: 1,
  DH: 1,
  EH: 1,
  ACH: 1,
  ADH: 1,
  AEH: 1,
  CDH: 1,
  CEH: 1,
  DEH: 1,
  ACDH: 1,
  ACEH: 1,
  ADEH: 1,
  CDEH: 1
}

3. 조건에 맞은 조합만 선별합니다.

[ 'AC', 'CDE', 'BCFG', 'ACDE' ]

4. 알파벳 오름차순으로 정렬합니다.

["AC", "ACDE", "BCFG", "CDE"]

 

 

 

전체 코드

function solution(orders, course) {
  // orders 배열의 각 주문에 대해 모든 가능한 조합을 구하고 중복을 체크하여 orderData에 저장
  const orderData = getOrderData(orders, course);
  
  // course 배열에 있는 길이 중에서 최대 주문 횟수를 가진 조합을 찾음
  const result = course.reduce((acc, courseLength) => {
    let maxCount = 0;
    const candidates = [];

    for (const order in orderData) {
      if (isValidCourseLengthAndOrderCount(order, courseLength, orderData)) {
        if (orderData[order] > maxCount) {
          candidates.length = 0; // 현재 길이의 조합 중 최대 주문 횟수를 가진 조합이 변경되면 후보 배열 초기화
          maxCount = orderData[order];
        }

        if (orderData[order] === maxCount) {
          candidates.push(order);
        }
      }
    }

    acc.push(...candidates);
    return acc;
  }, []);

  return result.sort(); // 결과를 알파벳 순서로 정렬하여 반환
}

function getOrderData(orders, course) {
  return orders.reduce((acc, order) => {
    const orderArray = [...order].sort(); // 주문을 알파벳 순서로 정렬
    const orderLength = orderArray.length; // 주문 문자열의 길이

    // course 배열에 있는 길이의 조합을 구함
    for (const courseLength of course) {
      if (courseLength > orderLength) continue; // 주문 문자열의 길이보다 긴 조합은 무시
      const combinations = getCombinations(orderArray, courseLength);
   
      for (const combo of combinations) {
        const key = combo.join(''); // 조합을 문자열로 변환하여 키로 사용
        acc[key] = (acc[key] || 0) + 1; // 중복 카운트 증가
      }
         
    }
    return acc;
  }, {});
}

// 조합을 구하는 함수
function getCombinations(orderArray, courseLength) {
  const result = [];
  function dfs(start, current) {
    if (current.length === courseLength) {
      result.push([...current]);
      return;
    }

    for (let i = start; i < orderArray.length; i++) {
      current.push(orderArray[i]);
      dfs(i + 1, current);
      current.pop();
    }
  }

  dfs(0, []);
  return result;
}


function isValidCourseLengthAndOrderCount(order, courseLength, orderData) {
  return order.length === courseLength && orderData[order] >= 2;
}

 

 

카카오 문제 해설

공식 해설 링크

---

다른 사람 풀이

function solution(orders, course) {
  const ordered = {};
  const candidates = {};
  const maxNum = Array(10 + 1).fill(0);
  const createSet = (arr, start, len, foods) => {
    if (len === 0) {
      ordered[foods] = (ordered[foods] || 0) + 1;
      if (ordered[foods] > 1) candidates[foods] = ordered[foods];
      maxNum[foods.length] = Math.max(maxNum[foods.length], ordered[foods]);
      return;
    }

    for (let i = start; i < arr.length; i++) {
      createSet(arr, i + 1, len - 1, foods + arr[i]);
    }
  };

  orders.forEach((od) => {
    // arr.sort는 기본적으로 사전식 배열
    const sorted = od.split('').sort();
    // 주문한 음식을 사전순으로 배열해서 문자열을 만든다.
    // course에 있는 길이만 만들면 된다.
    course.forEach((len) => {
      createSet(sorted, 0, len, '');
    });
  });

  const launched = Object.keys(candidates).filter(
    (food) => maxNum[food.length] === candidates[food]
  );

  return launched.sort();
}

link