[Java] 2021 카카오 블라인드 메뉴 리뉴얼

문제 설명

---

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

손님 번호주문한 단품메뉴 조합

1번 손님	A, B, C, F, G
2번 손님	A, C
3번 손님	C, D, E
4번 손님	A, C, D, E
5번 손님	B, C, F, G
6번 손님	A, C, D, E, H

가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

코스 종류메뉴 구성설명

요리 2개 코스	A, C	1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스	C, D, E	3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스	B, C, F, G	1번, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스	A, C, D, E	4번, 6번 손님으로부터 총 2번 주문됐습니다.

---

[문제]

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

• orders 배열의 크기는 2 이상 20 이하입니다.
• orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
  • 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
  • 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
• course 배열의 크기는 1 이상 10 이하입니다.
  • course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
  • course 배열에는 같은 값이 중복해서 들어있지 않습니다.
• 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
  • 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
  • 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
  • orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.

---

[입출력 예]

orderscourseresult

["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]	[2,3,4]	["AC", "ACDE", "BCFG", "CDE"]
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]	[2,3,5]	["ACD", "AD", "ADE", "CD", "XYZ"]
["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]

입출력 예에 대한 설명

---

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
AD가 세 번, CD가 세 번, ACD가 두 번, ADE가 두 번, XYZ 가 두 번 주문됐습니다.
요리 5개를 주문한 손님이 1명 있지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 5개로 구성된 코스요리는 새로 추가하지 않습니다.

입출력 예 #3
WX가 두 번, XY가 두 번 주문됐습니다.
3명의 손님 모두 단품메뉴를 3개씩 주문했지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 3개로 구성된 코스요리는 새로 추가하지 않습니다.
또, 단품메뉴를 4개 이상 주문한 손님은 없으므로, 요리 4개로 구성된 코스요리 또한 새로 추가하지 않습니다.

 

 

 

접근 방법

---

 HashMap과 backTracking을 적절히 활용하여 해결할 수 있는 문제였습니다.

 

1. 문제를 해결하기에 앞서 orders를 정렬 해야합니다. 한 예시로 xy와 yx는 같은 조합으로 볼 수 있고, 이러한 경우를 수월하게 계산하기 위해 사전순으로 정렬합니다.

 

2. 최소 2번 이상 주문된 음식의 조합(backTracking)을 HashMap에 저장합니다. (HashMap<String 음식조합, Integer 주문횟수>) 

 

3. HashMap의 원소를 각각 탐색하면서 음식조합의 수가 course의 한 요소와 일치한다면 가장 많이 주문된 횟수를 비교 갱신하며 음식조합 또한 추가 혹은 갱신을 합니다. 이 때 아래 2개의 HashMap을 사용하였습니다.

 (1) HashMap<Integer, ArrayList<String>> maxMap = new HashMap<Integer, ArrayList<String>>(); 
 (2) HashMap<Integer, Integer> maxCnt = new HashMap<Integer, Integer>();  

 

maxMap은 음식조합의 수(course)에 따른 음식조합을 저장합니다. 만약 한 음식 조합의 주문된 횟수가 최대 주문 횟수랑 일치하는 경우 요소를 추가해야 하기 때문에 value는 List의 형태를 가져야 합니다.

maxCnt는 음식조합의 수(course)에  따른 주문된 최대 횟수를 저장합니다.

 

자세한 내용은 아래 소스코드에 주석으로 설명하겠습니다.

 

 

소스 코드

---

import java.util.*;
import java.lang.*;

class Solution {
    
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    HashMap<Integer, ArrayList<String>> maxMap = new HashMap<Integer, ArrayList<String>>(); 
    HashMap<Integer, Integer> maxCnt = new HashMap<Integer, Integer>(); 
    
    public void backTracking(int n, int cnt, int now, String order, String comb){
        
        if(cnt == n){
            if(map.containsKey(comb)){ //이미 주문된 적 있는 조합이라면
                int orderCnt = map.get(comb);
                map.put(comb, orderCnt + 1); // 주문횟수 1증가
            }
            else
                map.put(comb, 1);
        }
        for(int i = now; i<order.length(); i++){
            comb += order.charAt(i);
            backTracking(n, cnt+1, i + 1, order, comb);
            comb = comb.substring(0, comb.length() - 1);
        }
    }
    
    public ArrayList<String> solve(String[] orders, int[] course){
        
        ArrayList<String> ans = new ArrayList<String>();
        
        //1번 과정, 수월한 풀이를 위해 문자열 사전순 정렬
        for(int i=0;i<orders.length;i++){
            char[] tmp = orders[i].toCharArray();
            Arrays.sort(tmp);
            orders[i] = new String(tmp);
        }
        
        //2번 과정, i번째 주문에 대해 ,j개(최소 2개) 이상의 조합을 구함
        for(int i=0;i<orders.length;i++)
            for(int j=2;j<=orders[i].length();j++)
                backTracking(j,0,0,orders[i], "");    
        
        //course를 map에 미리 매핑시킴, 이후 course의 요소인지 판별하기에 쉽게 이용 가능
        for(int i=0;i<course.length;i++){
            maxMap.put(course[i], new ArrayList<String>()); 
            maxCnt.put(course[i], 0); 
        }
        
        //3번 과정
        for(Map.Entry<String, Integer> elem : map.entrySet()){
            String foods = elem.getKey();
            int cnt = elem.getValue();
            if(cnt >= 2){
                if(maxMap.containsKey(foods.length())){ //course의 요소라면
                    if(maxCnt.get(foods.length()) == cnt){ //최대 주문 횟수와 일치한다면
                        maxMap.get(foods.length()).add(foods); //추가
                    }
                    else if(maxCnt.get(foods.length()) < cnt){ //최대 주문 횟수 보다 더 크다면
                        maxCnt.put(foods.length(), cnt); //최댓값 갱신
                        ArrayList<String> newOne = new ArrayList<String>(Arrays.asList(foods)); 
                        maxMap.put(foods.length(), newOne); //새롭게 갱신
                    }
                }
            }   
        }
        
        //결과들을 ArrayList에 담는다.
        for(ArrayList<String> elem : maxMap.values())
            for(int i=0;i<elem.size();i++)
                ans.add(elem.get(i));    
        
        //사전순 정렬
        Collections.sort(ans);
        
        return ans;
    }
    
    public String[] solution(String[] orders, int[] course) {
        ArrayList<String> ans = solve(orders, course);
        String[] answer = ans.toArray(new String[ans.size()]);
        return answer;
    }
}