문제
문제 분석
배열이 두개가 주어지는데 orders와 course가 각각 무엇을 의미하는지와 어떻게 메뉴를 조합하는지를 잘 정해야 합니다.
풀이
어려웠던 점
이전에 뉴스클러스터링 문제와 많이 혼돈이 되었었습니다. (https://velog.io/@ds02168/1%EC%B0%A8-%EB%89%B4%EC%8A%A4-%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0%EB%A7%81)
한개씩 끊는것이 아니라 조합을 이용하여 메뉴들을 무작위로 갯수에 맞게 조합해야 합니다.
조합에 대해 생소하신 분들은 먼저 조합에 대해 익히시는것이 좋을것 같습니다.
## 목차 1. 문자열을 문자단위로 분리 2. 조합 3. 단품갯수당 최대 빈도 구하기 4. 메뉴 후보 구하기
문자열을 문자단위로 분리
//메뉴의 조합 구하기
for(int i=0;i<course.length;i++){
for(int j=0;j<orders.length;j++){
String[] order = orders[j].split("");
int n = orders[j].length();
boolean[] visited = new boolean[n];
combination(order,visited,0,n,course[i]); //조합
}
}문자열을 String[] order에 문자하나씩 저장하고, n에 문자열의 길이, 조합을 위한 boolean[] visited를 조합에 이용합니다.
조합
//조합
//order[]는 문자, visited[]는 방문, start는 시작인덱스, nCr에서 n개중에 r개의 조합
public static void combination(String[] order, boolean[] visited, int start, int n, int r){
if(r == 0){
String key = "";
for(int i=0;i<n;i++){ //조합 결과
if(visited[i]){
key += order[i];
}
}
//정렬
char[] temp = key.toCharArray();
Arrays.sort(temp);
key = new String(temp);
if(!hash.containsKey(key))
hash.put(key,1);
else
hash.put(key,hash.get(key)+1);
return;
}
for(int i =start;i<n;i++){
visited[i] = true;
combination(order,visited,i+1,n,r-1);
visited[i] = false;
}
}매개변수 중 start : 시작 위치이고, n : n개중 r : 개 를 뽑는다 즉 nCr로 조합을 구한다 생각하시면 됩니다.
if(r == 0) 일때가 갯수에 맞게 조합이 완성 되었을때 입니다. 항상 정렬을 해야 하므로 해시에 넣기전 정렬을 하고 넣습니다.
단품갯수당 최대 빈도 구하기
//각 메뉴갯수당 후보가 가능한 횟수, 즉 메뉴당 최댓값 구하기
Iterator<String> keys = hash.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
int menu_num = key.length();
if(hash.get(key) < 2) //1번만 나왔으면
continue;
if(!max.containsKey(menu_num)) //해당 길이 주문이 처음일때
max.put(menu_num,hash.get(key));
else{ //이미 다른 주문이 존재시
if(max.get(menu_num) < hash.get(key)) //이전의 주문 조합보다 횟수가 더많으면
max.put(menu_num,hash.get(key)); //바꿈
}
}Iterator을 이용하여 해시에 존재하는 키들을 모두 조회 합니다. 키마다 2번이상 나오는지, 해당 메뉴가 후보인지(갯수에서 최댓값인지) 구별하기 위해 max 해시에 단품 갯수당 최대 반복 횟수를 저장합니다.
메뉴 후보 구하기
//코스요리 메뉴 후보 출력
keys = hash.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
int menu_num = key.length(); //조합의 횟수
if(hash.get(key) == max.get(menu_num)) //코스메뉴 후보면
result.add(key);
}
Collections.sort(result); //정렬
return result.toArray(new String[0]);max해시에서 단품 갯수별 최대값과 동일한지 비교합니다. 같다면 가장 많이 나온 횟수와 동일하므로(ex: 'AB'는 단품 2개, 'DEF'는 단품 3개, 'ABEF'는 단품4개) 후보 메뉴가 됩니다.
코드
import java.util.*;
class Solution {
public static HashMap<String,Integer> hash = new HashMap<>(); //조합의 횟수를 저장하는 해시맵
public String[] solution(String[] orders, int[] course) {
ArrayList<String> result = new ArrayList<>();
HashMap<Integer,Integer> max = new HashMap<>(); //각 코스메뉴의 최대 크기
//메뉴의 조합 구하기
for(int i=0;i<course.length;i++){
for(int j=0;j<orders.length;j++){
String[] order = orders[j].split("");
int n = orders[j].length();
boolean[] visited = new boolean[n];
combination(order,visited,0,n,course[i]); //조합
}
}
//각 메뉴갯수당 후보가 가능한 횟수, 즉 메뉴당 최댓값 구하기
Iterator<String> keys = hash.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
int menu_num = key.length();
if(hash.get(key) < 2) //1번만 나왔으면
continue;
if(!max.containsKey(menu_num)) //해당 길이 주문이 처음일때
max.put(menu_num,hash.get(key));
else{ //이미 다른 주문이 존재시
if(max.get(menu_num) < hash.get(key)) //이전의 주문 조합보다 횟수가 더많으면
max.put(menu_num,hash.get(key)); //바꿈
}
}
//코스요리 메뉴 후보 출력
keys = hash.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
int menu_num = key.length(); //조합의 횟수
if(hash.get(key) == max.get(menu_num)) //코스메뉴 후보면
result.add(key);
}
Collections.sort(result); //정렬
return result.toArray(new String[0]);
}
//조합
//order[]는 문자, visited[]는 방문, start는 시작인덱스, nCr에서 n개중에 r개의 조합
public static void combination(String[] order, boolean[] visited, int start, int n, int r){
if(r == 0){
String key = "";
for(int i=0;i<n;i++){ //조합 결과
if(visited[i]){
key += order[i];
}
}
//정렬
char[] temp = key.toCharArray();
Arrays.sort(temp);
key = new String(temp);
if(!hash.containsKey(key))
hash.put(key,1);
else
hash.put(key,hash.get(key)+1);
return;
}
for(int i =start;i<n;i++){
visited[i] = true;
combination(order,visited,i+1,n,r-1);
visited[i] = false;
}
}
}GitHub
오늘도 내일도 화이팅!