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

문제

---

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

 

[제한사항]

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

 

 

 

풀이

---

course 에서 원하는 만큼의 갯수를 조합하여 메뉴구성을 만들었다.

 

좀 더 시간효율이 좋은 코드를 생각해봐도 좋을 것같다.

 

깊이 우선탐색 방식을 이용하여 알파벳 오름차순으로 정렬된 배열을 하나씩 더해가면 조합을 하는 방식을 사용하였다.

static void dfs(String[] menu, String result,int index, int count, int size){
	if(count == size){          
		if(map.containsKey(result)){                
			int cnt = map.get(result) + 1;
			if(max < cnt){
				max = cnt;
			}

			map.put(result, cnt);
		}
   		else{
   			map.put(result, 1);
		}            
		return;
	}

	for(int i = index; i < menu.length ; i++){
		dfs(menu, result + menu[i], i + 1, count + 1, size);
  	}        
}

그때 그때의 max 값의 크기를 조정하여 max와 같은 크기를 가진 메뉴구성을 모두 list에 넣어준다.

 

 

<전체코드>

import java.util.*;

class Solution {
    
    static HashMap<String, Integer> map;
    static int max;
    public String[] solution(String[] orders, int[] course) {
        String[] answer;
        
        
        List<String> list = new ArrayList<String>();
        for(int j = 0 ; j < course.length ; j++){
            map = new HashMap<String, Integer>();
            max = 0;
            for(int i = 0 ; i < orders.length ; i++){

                String[] menu = orders[i].split("");
                Arrays.sort(menu);
               
                if(menu.length >= course[j]){                   
                    dfs(menu, "", 0, 0, course[j]);                    
                }
            }
            
            for(String courses : map.keySet()){
                if(max >= 2 && map.get(courses) == max){
                    list.add(courses);
                }
            }
        }
         
        
        Collections.sort(list);
        answer = new String[list.size()];
        
        int i = 0;
        for(String courses : list){
            answer[i++] = courses;
        }
        
        return answer;
    }
    
    static void dfs(String[] menu, String result,int index, int count, int size){
        if(count == size){          
            if(map.containsKey(result)){                
                int cnt = map.get(result) + 1;
                if(max < cnt){
                    max = cnt;
                }
                    
                map.put(result, cnt);
            }
            else{
                map.put(result, 1);
            }            
            return;
        }
    
        for(int i = index; i < menu.length ; i++){
            dfs(menu, result + menu[i], i + 1, count + 1, size);
        }        
    }
}