프로그래머스(Java)-메뉴 리뉴얼

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/72411

문제 풀이

makeCourse 라는 재귀 함수를 통해서 현재코스 course[i]의 길이로 orders[j]에 있는 문자들로 새로운 문자열을 만들어서 arr에다가 넣게 된다.

makeCourse에서 만약에 course의 길이가 만들수 있는 문자들의 갯수 보다 크다면 애초에 만들수가 없ㄷ으므로 return 해주고, 만들고 있는 단어의 길이와 course가 같은 경우에 이제 arr에다가 만든 단어를 추가해준다.

단어를 추가하는 과정은 기본적인 dfs의 틀을 따랐다. 해당 단어를 방문했는지 체크한뒤, 방문한적이 없는 단어라면 현재 단어 뒤에다가 추가하고, makeCourse를 탈출하면서 추가했던 단어를 제거한다.

public void makeCourse(String [] order,int[] chk, int course, String word, int idx){
        if(course>order.length){
            return;
        }
        if(word.length()==course){
            arr.add(word);
            return;
        }
        for(int i=idx; i<order.length; i++){
            if(chk[idx]!=0){
                continue;
            }
            word+=order[i];
            chk[idx]=1;
            makeCourse(order,chk,course,word,i+1);
            chk[idx]=0;
            word=word.substring(0,word.length()-1);
        }
    }

arr에 있는 단어들을 값들이 총 몇번이 사용되었는지 map을 사용하여 체크한다.
arr에 있는 단어들이 key값, 사용횟수를 value로 가진다.

        for(int k=0; k<arr.size(); k++){
           String temp = arr.get(k);
           int count = cookMap.containsKey(temp) ? cookMap.get(temp)+1 : 1;
           cookMap.put(temp,count);
        }

현재 단어와(entry.getKey())의 길이, course의 값(course[i])이 같고, 2번 이상은 사용된 메뉴에 대해서는 후보에 넣어줘야한다.
해당 courese[i]에서의 최대값과 등장횟수(entry.getValue())값이 같은 경우에는 추천메뉴들을 임시보관할 temp에다가 값을 추가한다.

하지만 최대값(max)과 비교하여 등장횟수(entry.getValue())값이 더 큰경우에는 이전에 추가되었던 메뉴들은 필요가 없기때문에 temp값을 clear해서 값들을 모두 제거하고 일단temp에 메뉴를 추가하고, 최대값을 갱신한다.
모든 cookMap을 체크가 끝났을때 다음 course[i]로 넘어가기전에 최종적으로 메뉴를 출력할 result에 temp값들을 모두 저장한다.

 List<String>result = new ArrayList<>();
        for(int i=0; i<course.length; i++){
            int max = -1;
            List<String> temp = new ArrayList<>();
            for(Map.Entry<String,Integer> entry : cookMap.entrySet()){
                //System.out.println("key : " + entry.getKey() + "length"+entry.getKey().length() +", value : " + entry.getValue());
                if(entry.getKey().length()==course[i] && entry.getValue()>=2){
                    if(max<entry.getValue()){
                        max = entry.getValue();
                        temp.clear();
                        temp.add(entry.getKey());
                    }else if(max==entry.getValue()){
                        temp.add(entry.getKey());
                    }else{  
                    }
                }
            }
            for(int k=0; k<temp.size(); k++){
                result.add(temp.get(k));
            }
        }

마지막으로 정렬하고 출력한다.

코드

import java.util.*;

class Solution {
    
    static List<String> arr = new ArrayList();
    
    public String[] solution(String[] orders, int[] course) {

        Map<String,Integer>cookMap =new HashMap<>();
        for(int i=0; i<course.length;i++){
            for(int j=0; j<orders.length; j++){
                String [] order = orders[j].split("");
                Arrays.sort(order);
                int [] chk = new int[order.length];
                makeCourse(order,chk,course[i],"",0);
            }
        }
        for(int k=0; k<arr.size(); k++){
           String temp = arr.get(k);
           int count = cookMap.containsKey(temp) ? cookMap.get(temp)+1 : 1;
           cookMap.put(temp,count);
        }
        // System.out.println(arr.toString());
        // System.out.println(cookMap.toString());
        List<String>result = new ArrayList<>();
        
        for(int i=0; i<course.length; i++){
            int max = -1;
            List<String> temp = new ArrayList<>();
            for(Map.Entry<String,Integer> entry : cookMap.entrySet()){
                //System.out.println("key : " + entry.getKey() + "length"+entry.getKey().length() +", value : " + entry.getValue());
                if(entry.getKey().length()==course[i] && entry.getValue()>=2){
                    if(max<entry.getValue()){
                        max = entry.getValue();
                        temp.clear();
                        temp.add(entry.getKey());
                    }else if(max==entry.getValue()){
                        temp.add(entry.getKey());
                    }else{
                        
                    }
                }
            }
            for(int k=0; k<temp.size(); k++){
                result.add(temp.get(k));
            }

        }
        Collections.sort(result);
        
        String[] answer = result.toArray(new String[result.size()]);
        return answer;
    }
    
    public void makeCourse(String [] order,int[] chk, int course, String word, int idx){
        
        if(course>order.length){
            return;
        }
        
        if(word.length()==course){
            arr.add(word);
            return;
        }
        
        
        for(int i=idx; i<order.length; i++){
            if(chk[idx]!=0){
                continue;
            }
            word+=order[i];
            chk[idx]=1;
            makeCourse(order,chk,course,word,i+1);
            chk[idx]=0;
            word=word.substring(0,word.length()-1);
        }

    }
}