프로그래머스 LV2. 메뉴 리뉴얼 (자바)

🍀 문제

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

 

[입출력 예]

orders	course	result
["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"]

 

 

 

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

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

 

 

 

😊 나의 코드

import java.util.*;
class Solution {
    HashMap<String,Integer> menuMap = new HashMap();
    public String[] solution(String[] orders, int[] course) {
        for(int i=0; i<orders.length; i++) {//orders의 문자열 오름차순 정렬
            char[] charArr =orders[i].toCharArray();
            Arrays.sort(charArr);
            orders[i] = new String(charArr);
        }

        TreeSet<String> answerSet = new TreeSet();
        for(int i=0; i<course.length; i++) {
            menuMap.clear();
            for(int j=0; j<orders.length; j++) {
                if(orders[j].length()==course[i]) {
                    menuMap.put(orders[j], menuMap.getOrDefault(orders[j], 0)+1);
                }else if(orders[j].length()>course[i]) {
                    combination(course[i],0,orders[j], "");//메뉴 조합 구하기
                }
            }

            //map value 값으로 정렬
            if(menuMap.size()>0) {
                List<String> keySetList = new ArrayList<String>(menuMap.keySet());
                Collections.sort(keySetList, (o1, o2) -> (menuMap.get(o2).compareTo(menuMap.get(o1))));
                int max = menuMap.get(keySetList.get(0));
                if(max>=2) {// 최소 2명 이상 주문된 조합만 후보 포함
                    for(String key:keySetList) {
                        if(max==menuMap.get(key)) {
                            answerSet.add(key);
                        }else {
                            break;
                        }
                    }
                }
            }
        }

        String[] answer = new String[answerSet.size()];
        int index = 0;
        for(String a:answerSet) {
            answer[index++] = a;
        }
        return answer;
    }

    public void combination(int r, int index,String order, String combo) {
        if(r==0) {
            menuMap.put(combo, menuMap.getOrDefault(combo, 0)+1);
        }else if(index < order.length()){
            combination(r-1, index+1, order, combo+order.charAt(index));//선택한 경우
            combination(r, index+1, order, combo);//선택하지 않은 경우
        }
    }
}

 

 

1. 먼저, orders의 주문목록을 알파벳 오름차순으로 정렬

2. menuMap (key:메뉴조합 / value:주문횟수) 에 조합계산하여 담기

- orders의 메뉴개수와 course 메뉴개수 같으면 바로 menuMap에 담기

- orders의 메뉴개수가 더 크면 조합 계산 (combination)

3. 최소 2건 이상 && 제일 많이 나온 조합을 answerSet에 담기

4. answerSet을 리턴형식인 String[] 배열에 담고 리턴!

 

 

- String형 문자내 오름차순 정렬

String str = "CBA"; //정렬할 문자열
char[] charArr = str.toCharArray();
Arrays.sort(charArr); // 정렬
str = new String(charArr); // "ABC"로 정렬됨!

- 메뉴 조합은 combination 메소드를 사용

     nCr = n-1Cr-1 + n-1Cr

- 정답은 오름차순 정렬해서 return해야하기에 treeSet에 정답을 저장했다. (treeSet은 자동 정렬)