프로그래머스 : 메뉴 리뉴얼 (2021 KAKAO BLIND RECRUITMENT)

Link

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

Code

import java.util.*;
class Solution {
     public String[] solution(String[] orders, int[] course) {
        String[] answer = {};
        HashMap<String, Integer> map = new HashMap<>();

        for(int i = 0 ; i < orders.length; i++){
            HashSet<String> set = new HashSet<>();
            char[] charArr = orders[i].toCharArray();
            Arrays.sort(charArr);
            String result = new String(charArr);
            solve(set, course, result);
            for(String s : set){

                if(map.get(s)==null){
                    map.put(s,1);
                }
                else{
                    map.put(s,map.get(s)+1);
                }
            }
        }
        HashMap<Integer, String> map2 = new HashMap<>();
        HashMap<Integer, Integer> map3 = new HashMap<>();
        for(String s : map.keySet()){
               for(int i : course){

                   if(i == s.length() && map.get(s) != 1){

                       System.out.println("map: " + s +"- "+ map.get(s) + " map2: " + map2.get(i) + " map3: " + map3.get(i)  );
                       if(map2.get(i)== null){
                           map2.put(i , s);
                           map3.put(i , map.get(s));
                       }else{
                           if(map3.get(i) > map.get(s)){
                           }else if(map3.get(i) == map.get(s)){
                               map2.put(i, map2.get(i) +"-"+s);
                           }else{
                               map2.put(i , s);
                               map3.put(i , map.get(s));
                           }
                       }
                   }
               }
        }
        ArrayList<String> list = new ArrayList<>();
        for(int i : map2.keySet()){
            String[] s = map2.get(i).split("-");
            for(int j = 0 ; j < s.length ; j++){
                if(map3.get(i)!=1) {
                    list.add(s[j]);
                }
            }
        }
        answer = new String[list.size()];
        for(int i = 0 ; i < answer.length ; i ++){
            answer[i] = list.get(i);
        }

        Arrays.sort(answer);
        return answer;
    }
    public void solve(HashSet<String> set, int[] course, String data){

        if(data.length() == 1){
            return;
        }

        for(int j : course){
            if(j == data.length()){
                set.add(data);
            }
        }
        for(int i = 0 ; i <data.length(); i++){
            String data2 = data.substring(0, i) + data.substring(i+1);
            solve(set, course, data2);
        }
    }
}

Explain

1. 윗 그림과 같이 메뉴의 조합을 DFS로 모든 경우의 수를 구하여 중복된 값이 있을 수도 있으니 HashSet에 저장함 (course에 있는 길이만)

2. HashSet에 있는 값을 Map에 Key : 음식 조합 Value : 몇번을 택했는지? orders에 있는 값들을 전부 정리한다.

4. 다 끝난 후 메뉴 갯수 마다 최대 단골 메뉴를 선정해야하기 때문에 Key: 메뉴 갯수 value: 메뉴 이름과 Key: 메뉴 갯수 value: 메뉴 선택한 갯수를 선언하여 하나씩 처리해주고 만약 같은 선택한 갯수가 있을 경우 String에 ","을 붙쳐서 추가로 추가한다
5. 끝난 후 answer에 하나씩 삽입하여 이름 순서대로 출력하기 때문에 정렬사용