[level2] 프로그래머스 - 메뉴 리뉴얼(JAVA)
전체 코드는 맨 하단에 있습니다.
[ 문제 풀이 방법 ]
1. 각 손님이 주문한 메뉴(order)를 course개의 조합으로 만들 수 있는 모든 조합을 모두 만듭니다.
2. course[j]개의 조합 중, 가장 많이 선택 받은 수를 max[j]에 저장합니다.
3. 가능한 조합을 담아 둔 menu에서 메뉴 개수가 course[i]개면서 max[i]이고 2번 이상 선택된 메뉴를 담아 리턴합니다.
[ 코드 해석 ]
- 채택 될 메뉴의 개수를 아직 모르니, answer을 ArrayList로 선언해줍니다.
=> 나중에 리턴할 때 array로 바꿉니다.
ArrayList<String> answer = new ArrayList<String>();
- 각 개수별 최대 선택 횟수를 저장할 max배열과
가능한 모든 메뉴의 조합과 선택 횟수를 저장할 맵인 menu를 선언합니다.
max = new int[course.length];
menu = new HashMap<String, Integer>();
- 각 손님이 주문한 메뉴마다 course개의 조합으로 만들 수 있는 모든 조합을 찾아줍니다.
문제에서 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다. 라고 했으므로 미리 알파벳 순으로 정렬 합니다.
정렬된 '고객이 선택한 메뉴(order[i])'는 전역변수로 선언된, str에 저장합니다. => comb에서 사용
for (int i = 0; i < orders.length; i++) {
// 각 손님이 주문한 메뉴를 알파벳 순으로 정렬
char a[] = orders[i].toCharArray();
Arrays.sort(a);
str = String.copyValueOf(a); // 문자열로 바꿔서 가지고 있는다.
// course[j]개의 조합으로 만들 수 있는 모든 조합을 찾는다.
for (int j = 0; j < course.length; j++) {
isVisited = new boolean[str.length()];
comb(0, 0, "", j, course[j]);
}
}
- 조합 함수
=> comb(int cur, int cnt, String s, int j, int N)
int cur : 이제 선택할 문자의 위치(메뉴가 적힌 자리)를 가리킴
int cnt : 현재까지 선택된 메뉴의 개수를 가리킴
String s : 현재까지 선택된 메뉴의 조합
int N : course[]에 해당하는 값, 선택해야 하는 메뉴의 개수
- N개를 모두 선택 할 때 까지 재귀호출하여, N개 뽑을 수 있는 모든 경우의 수를 구합니다.
- 구한 경우의 수는 menu에 넣고, 몇 번 선택되었는지 저장합니다.
- N(count[j])개를 고르는 경우의 수 중, 가장 많이 선택 된 수를 max[j]에 저장합니다.
private static void comb(int cur, int cnt, String s, int j, int N) {
if (cnt == N) {
menu.put(s, menu.containsKey(s) ? menu.get(s) + 1 : 1);
max[j] = Math.max(max[j], menu.get(s));
return;
}
for (int i = cur; i < str.length(); i++) {
isVisited[i] = true;
comb(i + 1, cnt + 1, s + str.charAt(i), j, N);
}
}
- menu에 적힌, 모든 경우의 수 중에서 다음의 모든 것을 만족하는 것을 answer에 넣는다.
1. course[i]개 선택
course[i] == s.length()
2. 2번 이상 선택 된 조합
max[i] != 1
3. course[i]개 선택한 메뉴의 조합 중에서 가장 많이 선택된 것
menu.get(s) == max[i]
- 마지막으로, ArrayList를 String 배열로 바꿔 리턴해준다.
answer.stream().sorted().map(s -> s).toArray(String[]::new);
[ 전체 코드 ]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
class Solution {
static String str;
static HashMap<String, Integer> menu;
static boolean isVisited[];
static int max[];
public static String[] solution(String[] orders, int[] course) {
ArrayList<String> answer = new ArrayList<String>();
max = new int[course.length];
menu = new HashMap<String, Integer>();
for (int i = 0; i < orders.length; i++) {
char a[] = orders[i].toCharArray();
Arrays.sort(a);
str = String.copyValueOf(a);
for (int j = 0; j < course.length; j++) {
isVisited = new boolean[str.length()];
comb(0, 0, "", j, course[j]);
}
}
for (String s : menu.keySet())
for (int i = 0; i < course.length; i++)
if (course[i] == s.length() && max[i] != 1 && menu.get(s) == max[i])
answer.add(s);
return answer.stream().sorted().map(s -> s).toArray(String[]::new);
}
private static void comb(int cur, int cnt, String s, int j, int N) {
if (cnt == N) {
menu.put(s, menu.containsKey(s) ? menu.get(s) + 1 : 1);
max[j] = Math.max(max[j], menu.get(s));
return;
}
for (int i = cur; i < str.length(); i++) {
isVisited[i] = true;
comb(i + 1, cnt + 1, s + str.charAt(i), j, N);
}
}
}
혹시
이해가 안 가거나 잘 못 된 것이 있으면,
댓글 부탁드립니다 :)