프로그래머스 [메뉴 리뉴얼] - 순열과 조합, 해시 Lv.2

순열과 조합

• 순열과 조합 개념에 대해 알고, 이를 구현한 알고리즘을 숙지하고 있었기 때문에 풀이가 수월했다.
• 초기 문제 풀이 시, 조합 알고리즘을 떠올리기는 했지만 더 효율적인 시간 복잡도로 풀이할 수 없을까 고민하다가, 입출력 조건을 다시 꼼꼼하게 보니 입출력 제한을 넉넉하게 준 것 같아 조합 알고리즘을 이용하였다.

해쉬 테이블

• 또한 데이터 등장한 횟수 + 해당 데이터가 다른 인덱스에서도 똑같이 등장하는지? 에 관한 정보도 필요했기 때문에 데이터에 따라 세부적인 정보를 저장하는 것이 필요하였다. 따라서 해쉬 테이블로 자료에 관한 정보를 저장하여 풀었다.

풀이 전 로직

• 시작하기에 앞서 주문목록 내부 문자열들을 사전 순서로 정렬한다. 예시 케이스를 보니 주문 목록이 정렬이 되어있지 않기 때문이고, 추후에 정리하려면 데이터가 불어나서 까다롭기 때문에 미리 해두는 것이 편하다.
• 코스 메뉴를 구성할 단품 메뉴의 갯수들을 저장하고 있는 course 배열을 순회한다.
• 해당 순회 내부에서 주문 목록을 순회하며 코스 메뉴를 구성할 단품 갯수만큼을 조합해야하기 때문에, orders를 추가로 순회한다.
• 주문 목록을 하나씩 순회하며, 미리 정의해둔 조합 함수를 이용하여 코스 메뉴를 구성할 단품메뉴 만큼을 뽑아 배열에 저장한다.
• 모든 주문 목록에 대한 조합을 얻는 것을 완료했다면, 각 조합에 대해
  • 1) 해당 조합이 몇 번 등장하였는지 ?
  • 2) 다른 인덱스에서도 등장하였는지 ?
• 이 두가지 정보를 해쉬테이블 구조로 저장할 것이다.
• 1)번은 단순히 똑같은 것이 등장하면 count key의 value에 1을 더해주면 된다.
• 2)번은 조금 고민했는데.. 해당 조합이 처음 등장한 인덱스와 다른 인덱스가 추가로 등장한다면, person key의 value에 1을 더해주었다.
• 해당 문제에서 제시한 조건은, 적어도 2명(인덱스) 이상이 주문한 조합에 대해서만 코스로 구성해야 한다는 것이다. 따라서 filter 함수를 이용하여 person 값이 2 이상인 것만 필터링한다.
• 그리고 해당 해쉬테이블을 순회하며, count의 최대값을 알아낸 뒤, count가 해당 최대값을 가진 조합들을 filter 함수를 이용하여 필터링한다.
• 마지막으로 해당 조합들을 정답을 담을 배열에 push하고, 사전 순으로 정렬한다.

코드

function solution(orders, course) {
    function combinations(arr, n) {

  if (n === 1) return arr.map((v) => [v]);
  const result = [];

  arr.forEach((fixed, idx, arr) => {
    const rest = arr.slice(idx + 1);
    const combis = combinations(rest, n - 1);
    const combine = combis.map((v) => [fixed, ...v]);
    result.push(...combine);
  });
  return result;
}
    const answer = []
    // 1. course를 순회하며 course[i]개 만큼의 코스메뉴를 생성
    // 2. 이 안에서 orders를 순회하며, orders[j]를 이용하여 course[i]개 만큼 조합 알고리즘을 이용하여 뽑는다.
    // 3. 모든 주문 목록의 조합이 완성되면, 인덱스(주문자)가 다른 조합이면서 조합의 갯수가 많은 것을 뽑는다.
    // 4. 뽑힌 다수의 조합의 갯수가 많은 조합을 정답 배열에 넣는다.
    // 5. 정답 배열을 반환한다.
    orders = orders.map(item => item.split('').sort())
   
    for(let i = 0; i < course.length; i++) {  
        // num개의 코스메뉴를 생성하는게 목표
        const num = course[i]
        let menuArr = []
        for(let j = 0; j < orders.length; j++) {    // O(20)
            // num개를 뽑기 전, orders의 내부 요소들을 정렬하자.[x]
            // orders[j]에서 num개를 뽑아서 배열에 넣는다.[x]
            // 인덱스마다 뽑은 사람이 구분된다.
            // 따라서 인덱스가 다르면서 많이 뽑힌 조합을 찾아야한다.
            menuArr.push(combinations(orders[j], num))  //O(1024)
        }
        menuArr = menuArr.map(item => item.map(el => el.join('')))

        const menuMap = new Map()
       
        menuArr.forEach((item, index) => {
            for(let i = 0; i < item.length; i++) {
                const data = menuMap.get(item[i]) || {count: 0, person: 1, index}
                menuMap.set(item[i], {
                count: data.count + 1,
                person: data.index !== index ? data.person + 1 : data.person
                })
            }
        })
   
       const ans = [...menuMap].filter(item => item[1].person >= 2)
       let max = 0;
        for(let i = 0; i < ans.length; i++) {
            if(max <= ans[i][1].count) {
                max = ans[i][1].count
            }
        }
        answer.push(ans.filter(item => item[1].count === max).map(item => item[0]))
    }
    return answer.filter(item => item.length > 0).flatMap(item => item).sort()
}

후기

• 처음에 높은 시간 복잡도를 가진 조합 알고리즘을 써도 되나 많이 망설였지만, 입출력 조건을 보고 대입해보니 충분할 것 같았고, 통과하였다!
• 앞으로는 고민보다는 우선 대입부터 해보고, 다른 방법을 찾아보자.