[프로그래머스] 메뉴 리뉴얼 (java)

코딩테스트 연습 - 메뉴 리뉴얼 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

만들 수 있는 코스의 메뉴를 모두 나열하고, 코스의 단품메뉴 조합이 가장 많이 주문된 코스를 결과에 추가함으로서 문제를 해결하고자 하였습니다.

HashMap을 사용하여 코스 메뉴와 손님이 주문한 횟수를 연결짓고자 하였고 PriorityQueue를 사용하여 반환 결과의 정렬을 구현하고자 하였습니다.

코드

import java.util.PriorityQueue;
import java.util.HashMap;
import java.util.Arrays;
class Solution {
    HashMap<String, Integer> combinations;
    public String[] solution(String[] orders, int[] course) {
        PriorityQueue<String> compositions = new PriorityQueue<>();
        for(var k : course){
            //1. 각 메뉴로부터 메뉴를 조합 
            combinations = new HashMap<>();
            for(var order : orders){
                makeCombination(order,k,0,"");    
            }
            //2. 메뉴 조합을 전체 주문 목록에서 몇번 주문했는지 확인.
            int max=0;
            for(var menu : combinations.keySet()){
                int ordertimes = getOrderTimes(orders,menu.toCharArray());
                combinations.put(menu, ordertimes);
                if(ordertimes > max) max = ordertimes;
            }
            //3. 가장 많이 주문한 메뉴들을 PQ에 추가.
            for(var set : combinations.entrySet()){
                if(max>1 && set.getValue()==max) compositions.add(set.getKey());
            }
        }
        //4. PQ를 String 배열로 변환하여 반환.
        String[] answer = new String[compositions.size()];
        int k=0;
        while(!compositions.isEmpty()){
            answer[k++] = compositions.poll();
        }
        return answer;
    }
    public int getOrderTimes(String[] orders, char... menuArr){
        int count = 0;
        for(var order : orders){
            boolean ordered = true;
            for(var menu : menuArr){
                if(order.indexOf(menu)==-1) ordered = false;
            }
            if(ordered) count++;
        }
        return count;
    }
    public void makeCombination(String order, int k, int index, String result){
        //i위치에서 경우의 수 : 사용하거나, 사용하지 않거나
        if(result.length() == k) {
            char[] resulttochar = result.toCharArray();
            Arrays.sort(resulttochar);
            combinations.put(new String(resulttochar),0);
            return;
        }
        if(index < order.length()){
            makeCombination(order,k,index+1,result+order.charAt(index));
            makeCombination(order,k,index+1,result);    
        }
        return;
    }
}

설계를 바탕으로 코드를 작성하였습니다.

조합을 구현하는데 있어 index번째 단품메뉴는 조합에 포함되거나 포함되지 않거나 2가지 경우로 나뉘어 생각할 수 있기 때문에 재귀함수를 통해 해결하였습니다. 

조합으로 작성된 코스는 요리의 순서에 관계없어야 합니다.

Arrays.sort함수를 사용하여 순서가 달라 발생하는 중복을 방지할 수 있습니다.

PriorityQueue를 배열로 작성하여 결과를 반환하는데 있어 PriorityQueue는 Heap으로 이루어져 있다는 점에 유의하셔야 합니다.

Heap 구조는 부모 노드와 자식 노드간의 대소관계만을 지켜 작성된 트리구조이므로 두 자식노드간의 대소관계는 지켜져 있지 않습니다.

toString함수가 아닌 반복된 poll함수를 사용하여야 정렬된 배열을 반환할 수 있습니다.