[프로그래머스] 2021 카카오 / 메뉴 리뉴얼 (Java)

#2 메뉴 리뉴얼

2021 카카오 블라인드

난이도 : LEVEL 2

유형 : 조합/ Map / 정렬

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

[문제]

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

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

 

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

 

[제한사항]

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

 

문제 풀이

순열 조합과 Map을 사용하여 풀이하였다. 처음에는 어떻게 메뉴 조합 경우의 수를 뽑아줘야할까 고민을 좀 했었다. 주문의 각 알파벳을 꺼내와서 손님의 주문 문자열과는 상관없이 독립적으로 메뉴 갯수만 카운트를 하게되면 제일 많이 주문한 메뉴는 골라도 이게 어디에 속해있는지 메뉴 콤보는 알 방도가 없다.

 

그래서 나올 수 있는 모든 메뉴 조합 경우의 수를 다 뽑아준 다음 거기서 손님의 주문을 골라 카운트해주는 방식을 선택했다.

* ordes의 배열 각 원소 최대 크기는 10이다. 그러므로 메뉴의 종류는 총 10개이므로 모든 경우의 수를 뽑아줘도 괜찮다고 생각했다.

 

설계

1. 손님들이 주문한 orders에 속해있는 총 메뉴들(최대 10개)에 대한 모든 조합을 구한다.
2. 구한 경우의 수들을 모두 Map에 Key로 저장하고 그에 대한 count를 value값에 넣어준 다음 value를 기준으로 오름차순 정렬해준다.
3. 정렬한 값을 가지고 조건에 맞는 코스요리 메뉴를 담아 출력하면 된다.

 

구상

1번 로직

orders 배열에 담긴 값들을 모두 원소 2개 이상의 부분집합을 구할 것이다. orders와 courses의 최대 갯수가 그리 크지않아서 나올 수 있는 모든 코스메뉴 구성을 브루트포스로 다 조회할 것이다. 순서를 고려해주지 않아도 되므로 조합을 구해주면 된다.

ex) ABC

     > { AB, AC, BC, ABC }

 

2번 로직

1번에서 구한 모든 부분집합들을 Map에 저장하면서 카운트해주면 되므로 간단하다.  

• key : 코스메뉴 
• value :  해당 코스메뉴 주문 갯수 

그리고나서 Value를 기준으로 Map 오름차순 정렬을 해주면 된다.

 

3번 로직

오름차순으로 정렬된 주문된 정보들을 가지고 코스메뉴 갯수(coures)에 맞춰 후보들을 골라주면 된다. 문제에 최소 2명 이상이 시킨 메뉴만 후보에 넣고, 중복을 허용하므로 두 가지 조건만 고려하면 된다.

 

설계

1번 로직 코드

dfs탐색으로 가능한 조합을 모두 구한 다음 중복이 허용되므로 list에 저장하면 된다. 

combi = new ArrayList<>();
//코스 메뉴조합의 모든 경우의 수 구하기 (dfs) 
for(int i=0; i<orders.length; i++) {
	String[] one = orders[i].split("");
	Arrays.sort(one);
	
	for(int j=0; j< one.length-1; j++) {
		for(int k=0; k< course.length; k++) {
			dfs(one, j, 1, course[k], one[j]);
		}
	}
}

static void dfs(String[] one, int idx, int len, int courseLen, String str) {
	if(len == courseLen) {
		combi.add(str);
	}
	
	for(int i= idx+1; i<one.length; i++) {
		dfs(one, i, len+1, courseLen, str+one[i]);
	}
}

 

2번 로직 코드

Map 자료구조에 Key에는 1번에서 구한 조합을 넣어주고 Value에는 해당 조합의 갯수를 세어준다. 참고로 Map을 사용할 때 이 코드는 알아두는 것이 좋다. 완전 편하다.

map.put(menu, map.getOrDefault(menu, 0)+1); 

Map<String , Integer> map = new HashMap<>();
for(String menu : combi) {
    	map.put(menu, map.getOrDefault(menu, 0)+1);
}
   
List<String> list = new ArrayList<>(map.keySet());
Collections.sort(list, new Comparator<String>() {
	@Override
	public int compare(String o1, String o2) {
		return map.get(o2)-map.get(o1);
	}
});

 

☛ Map의 Key를 ArrayList에 담아 menu 갯수대로 정렬하였다.

 

1) 원래 List에 Entry를 사용해서 Comparator로 조합하고 그랬다.

// Map.Entry 리스트 작성
List<Entry<String, Integer>> list_entries = new ArrayList<Entry<String, Integer>>(testMap.entrySet());

// 비교함수 Comparator를 사용하여 오름차순으로 정렬
Collections.sort(list_entries, new Comparator<Entry<String, Integer>>() {
	// compare로 값을 비교
	public int compare(Entry<String, Integer> obj1, Entry<String, Integer> obj2) {
		// 오름 차순 정렬
		return obj1.getValue().compareTo(obj2.getValue());
	}
});

 

2) 근데 구글링을 해보니 재밌는 코드가 있어서 사용했다. 재밌는 점은 Map을 List에 옮긴다음에 get()메소드를 통해서 정렬을 했다는 점이다. List에는 key값만 옮길 수 있기 때문에 일부로 위의 방법으로 했던 것인데 위의 방법이 있다니 재밌다.

→ 이게 가능한 이유는 뒤에 사용할 데이터가 Key만 쓰이고 Value의 값은 더 이상 필요없기 때문이다. 

 List<String> list = new ArrayList<>(map.keySet());
 Collections.sort(list, new Comparator<String>() {

			@Override
			public int compare(String o1, String o2) {
				return map.get(o2)-map.get(o1);
			}
		});

// 그냥 람다식으로 표현해도 됨
// Collections.sort(keySetList, (o1, o2) -> (map.get(o2).compareTo(map.get(o1))));

 

3번 로직 코드

메뉴의 갯수대로 정렬된 List 데이터를 가지고 course의 갯수에 맞는 데이터를 뽑아주면 된다.

List<String> res = new ArrayList<>();
for(int i=0; i< course.length; i++) {
	int max =0;

	// course 갯수별로 가장 인기있는 품목 선정 
	for(String courseMenu : list) {
		if(map.get(courseMenu)>1 && courseMenu.length() == course[i]) {
			if(map.get(courseMenu) >= max) {
				res.add(courseMenu);
				max = map.get(courseMenu);
			}
		}
	}
}

// 문자순 정렬 
Collections.sort(res);

 

 

전체 풀이 코드 

import java.util.*;
class Solution {
    
    static List<String> combi;
    public String[] solution(String[] orders, int[] course) {
        String[] answer = {};
                
        combi = new ArrayList<>();
        //코스 메뉴조합의 모든 경우의 수 구하기 (dfs) 
        for(int i=0; i<orders.length; i++) {
        	String[] one = orders[i].split("");
        	Arrays.sort(one);
        	
        	for(int j=0; j< one.length-1; j++) {
        		for(int k=0; k< course.length; k++) {
        			dfs(one, j, 1, course[k], one[j]);
        		}
        	}
        }
        
        Map<String , Integer> map = new HashMap<>();
        for(String menu : combi) {
        	map.put(menu, map.getOrDefault(menu, 0)+1);
        }
        
       
        List<String> list = new ArrayList<>(map.keySet());
        Collections.sort(list, new Comparator<String>() {

			@Override
			public int compare(String o1, String o2) {
				return map.get(o2)-map.get(o1);
			}
		});

       
       List<String> res = new ArrayList<>();
       for(int i=0; i< course.length; i++) {
    	   int max =0;
    	   
    	   // course 갯수별로 가장 인기있는 품목 선정 
    	   for(String courseMenu : list) {
    		   if(map.get(courseMenu)>1 && courseMenu.length() == course[i]) {
    			   if(map.get(courseMenu) >= max) {
    				   res.add(courseMenu);
    				   max = map.get(courseMenu);
    			   }
    		   }
    	   }
       }
       
       // 문자순 정렬 
       Collections.sort(res);
    	
       answer = new String[res.size()];
       res.toArray(answer);
        
        
        return answer;
    }
    
    
	static void dfs(String[] one, int idx, int len, int courseLen, String str) {
		if(len == courseLen) {
			combi.add(str);
		}
		
		for(int i= idx+1; i<one.length; i++) {
			dfs(one, i, len+1, courseLen, str+one[i]);
		}
	}
}