[알고리즘 / 프로그래머스 / Java] 메뉴 리뉴얼 (2021 KAKAO BLIND RECRUITMENT)

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

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

해당 문제를 풀기 위해 많은 시간을 잡아먹었고, 특히나 단순 조합만을 이용하는 것이 아닌

여러 까다로운 조건들이 있어서 쉽지 않았던 문제였습니다.

처음에 접근할때는 손님기준으로 조합을 사용했었지만, 이는 여러 테스트 케이스에서 통과 되지않는 오류가 있어

손님별 메뉴 기준으로 조합을 사용했습니다. 아무래도 전자 방법을 이용하면 여러조건에서 탈락되는 부분이

많았기 때문에 제대로 동작하지 않았던 것 같습니다.

 

코드를 보기앞서 간단하게 로직의 순서를 살펴보면

1. 손님별 모든 주문에 대한 조합을 구한다. (각 주문을 각각 정렬뒤 조합로직)

2. 조합을 하되 문제에서 주어진 길이(course)를 가진 조합으로만 구성한다.

3. key에는 메뉴조합, value에는 메뉴중복개수를 가지는 Map을 구한다.

4. Map을 메뉴중복개수의 내림차순으로 정렬한다.

5. 문제 세부조건에 맞게 새로운 List를 작성한다. (최소 2명이상 선택한메뉴조합,
   코스요리를 구성하는 단품메뉴들의 갯수가 담긴 course고려)

6. 정답리스트를 사전순 오름차순으로 정렬한다.

 

<코드>

import java.util.*;

class Solution {
    List<String> combin;
    
    public String[] solution(String[] orders, int[] course) {
        combin = new ArrayList<String>();
        
        // 손님별 모든주문에 대하여 조합을 구함.
        for(int i=0; i<orders.length; i++) {
            char[] orderToChar = orders[i].toCharArray();
            Arrays.sort(orderToChar);   // XW == WX
            
            for(int j=0; j<orderToChar.length; j++) {
                for(int k=0; k<course.length; k++) {    // 주어진 코스길이만 조합.
                    dfs(orderToChar, j, 1, course[k], Character.toString(orderToChar[j]));
                }
            }
        }
        
        // 모든 조합에 대해 중복된 아이템을 묶음.(key로 메뉴조합, value로 중복개수)
        Map<String, Integer> map = new HashMap<>();
        for(String item : combin) {
            map.put(item, map.containsKey(item) ? map.get(item)+1 : 1);
        }
        List<String> keyList = new ArrayList<>(map.keySet());
        Collections.sort(keyList, (o1, o2) -> map.get(o2).compareTo(map.get(o1)));
        List<String> answerList = new ArrayList<>();
             
        // 출력확인..
        for(String key : keyList) {
            System.out.print(key+"("+map.get(key)+") ");
        }
        System.out.println();
        
        for(int i=0; i<course.length; i++) {
            int curValue = 0;
            for(String key : keyList) {
                if(map.get(key) >= 2 && key.length() == course[i]) {
                    if(map.get(key) >= curValue) {
                        answerList.add(key);
                        curValue = map.get(key);
                    } else break;
                } 
            }
        }

        Collections.sort(answerList);
        return answerList.toArray(new String[answerList.size()]);
    }
    
    public void dfs(char[] arr, int index, int curLen, int maxLen, String menus) {
        if(curLen == maxLen) {
            combin.add(menus);
        }
        
        for(int i=index+1; i<arr.length; i++) {
            dfs(arr, i, curLen+1, maxLen, menus+arr[i]);
        }
    }
}