[프로그래머스] 2021 KAKAO 블라인드 _ 메뉴 리뉴얼

2021_07_04 문제 풀이

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

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

 

문제

 

의사 코드

requirement 
  // course 별로 주문이 가장 많이된 거 한개 넣기, 값이 다 똑같으면 다 넣으면 됨
  // 최소 두명이상이 주문을 해야함


 course를 순회하면서 아래 로직 처리
 
   // orders를 filter메소드를 사용해서, 원소의 길이가 course 원소 이상인 것들만 필터링한다 (애초에 해당되지 않기때문)
     // 조합으로 처리 필요, 필터링 한 것들을 split, sort 메소드를 사용해 오름차순 정렬하고 join으로 붙인다
   // ex) ["ABCFG", "CDE", "ACDE", "BCFG", "ACDEH"], 2
 
   // 필터링된 요소들을 순회하며, 조합을 만들어낸다 ( 재귀함수 구현 )
   
   // course 원소를 이용, 그 조합들을 2차원 배열 형태로 저장> [["AB", "AC", "AF", "AG", "BC"...], [...];
    // 빈객체 선언 ex) { key : count}
      // 위 조합 배열 1차 순회
        // 조합배열의 원소를 순회 (이중 반복문)
          // 각 원소를 객체에 담는다
            // 만약 obj[el] === undefined일 경우 obj[el] = 1;
            // 그렇지 않다면, obj[el] = obj[el] + 1;

   // 객체의 키를 이용해서 객체를 순회한다 ( 최고 카운트를 뽑기위해 )
      // 카운트는 최소 2이상이어야 함 (2명 이상의 고객 주문)
      // let maxCount = 2;
      // obj[key] > count 인 경우 count는 obj[key]로 할당
      
  // maxCount가 2이상인 경우
    // 객체를 순회
      // obj[key]가 count 와 같은 것을 result 배열에 추가한다 (course[1] / 3에 대한 코스요리 선정 완료)

  // result를 sort 메소드를 사용, 정렬
  // 리턴한다

 

풀이

function combination(letters, pickNum) {
    let arr = [];
    
    function aux(str, lastIdx) {
        if (str.length === pickNum) {
            arr.push(str);
            return;
        }
        
        for (let i = lastIdx + 1; i < letters.length; i++) {
            aux(str + letters[i], i)
        }
    }
    aux("", -1)
    return arr;
}

function solution(orders, course) {
    let result = [];
    
    course.forEach((courseCount) => {
        let combMenus = [];
        let courseMenu = orders.filter((order) => order.length >= courseCount);
        
        const sortedCourseMenu = courseMenu.map((order) => order.split("").sort().join(""))
        
        sortedCourseMenu.forEach((menu) => combMenus.push(combination(menu, courseCount)))
        
        let combObj = {};
        combMenus.forEach((order) => {
            order.forEach((comb) => {
                if (combObj[comb] === undefined) {
                    combObj[comb] = 1;
                } else {
                    combObj[comb] = combObj[comb] + 1;
                }
            })
        })
        let maxCount = 0;
        for (const key in combObj) {

            if (combObj[key] >= maxCount) {
                maxCount = combObj[key];
            }
        }
        if (maxCount >= 2) {
            for (const key in combObj) {
                if (combObj[key] === maxCount) {
                    result.push(key);
                }
            }
        }
    })
    result.sort();
    return result;
}

 

 

조합을 어떻게 구현할 것인지 고민을 하다가 조합 알고리즘을 구글링하여 아래 블로그의 로직을 참고했다.

https://gorakgarak.tistory.com/523

조합(Combination) 알고리즘

combination 재귀함수의 시간 복잡도 : O(2^n)

solution 함수의 시간 복잡도 : O(n^3)

어마무시한 코드가 만들어졌다.

재귀함수를 이용하여, combination 함수를 구현했다.

이외에는 각 조합에 대한 count를 객체 형태에 담아 문제를 해결했다.

문제 해결은 했지만 재귀함수와 삼중 반복문을 사용해 작동 시간이 오래 걸린다.

더 좋은 해결책이 있는 지 조금 더 고민을 해봐야 할 것 같다.