2021 KAKAO BLIND RECRUITMENT
https://programmers.co.kr/learn/courses/30/lessons/72411
카카오 코테에 니니즈 등장하면 너무 심장 몽글몽글해져서 문제풀이 불가
🥚문제
🥚입력/출력
🧂아이디어
makeMenu(String[] orders)- orders에 등장하는 메뉴들(알파벳들)을 저장하는 ArrayList를 return
combination(ArrayList<Character> menu, int combi_number)- combi_number 개수로 이루어진 조합을 저장한 ArrayLIst를 return
- 입력값이
["XYZ", "XWY", "WXA"], [2, 3, 4]일 때, - 2개의 메뉴로 이루어진 조합
[XY, XZ, XW, XA, YZ, YW, YA, ZW, ZA, WA]
3개의 메뉴로 이루어진 조합
[XYZ, XYW, XYA, XZW, XZA, XWA, YZW, YZA, YWA, ZWA]
4개의 메뉴로 이루어진 조합
[XYZW, XYZA, XYWA, XZWA, YZWA]
와 같은 결과를 얻어냄 - 내부에서
makeCombination메소드가 중복 없이, 순서 관계 없이, 정해진 개수를 선택하는 조합을 재귀적으로 만들어내고 있음
countForCombination(ArrayList<String> combinations, String[] orders)combination메소드를 통해 만들어진 조합들이 손님들의 주문에서 등장하는 횟수를 카운트한 뒤, 그 정보를 담은 int[ ]를 리턴- 위
combination메소드의 설명과 입력값이 같다고 할 때 - 2개의 메뉴로 이루어진 조합
2, 1, 2, 1, 1, 1, 0, 0, 0, 1
3개의 메뉴로 이루어진 조합
1, 1, 0, 0, 0, 1, 0, 0, 0, 0
4개의 메뉴로 이루어진 조합
0, 0, 0, 0, 0
과 같은 결과를 얻어냄
findMaxIndex(int[] count_combinations)countForCombination을 통해 조합들이 등장하는 횟수를 카운트한 정보를 얻었으면, 그 중 가장 빈번하게 등장하는 조합들의 combination에서의 index를 찾는다. (최빈 조합을 찾아낸다)- 이때, 문제의 조건에서 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함한다고 했으므로 가장 빈번하게 등장하는 조합의 등장 횟수가 1 이하라면 max_index는 빈 배열을 리턴받는다.
findCourseMenu(combinations, max_index)- max_index를 활용해서 조합을 찾아낸다
combination메소드의 설명과 입력값이 같다고 할 때- 2개의 메뉴로 이루어진 조합
XY, XW
3개의 메뉴로 이루어진 조합
없음
4개의 메뉴로 이루어진 조합
없음
- 마지막으로, answer array를 구성할 때, 각각의 요소도 오름차순으로 정렬되어 있고, String array 전체도 오름차순으로 정렬하여 return함에 주의한다.
🍳코드
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public String[] solution(String[] orders, int[] course) {
// 임시로 결과를 담을 arraylist
ArrayList<String> temp = new ArrayList<>();
// orders에서 등장한 메뉴명을 arraylist에 저장
ArrayList<Character> menu = makeMenu(orders);
for(int i = 0; i < course.length; i++){
// course[i]개로 구성된 조합 구하기
// 예시
// [AB, AC, AF, AG, AD, AE, AH, BC, BF, BG, BD, BE, BH, CF, CG, CD, CE, CH, FG, FD, FE, FH, GD, GE, GH, DE, DH, EH]
ArrayList<String> combinations = combination(menu, course[i]);
// 조합들이 등장하는 횟수 count
// 에시
// [1, 4, 1, 1, 2, 2, 1, 2, 2, 2, 0, 0, 0, 2, 2, 3, 3, 1, 2, 0, 0, 0, 0, 0, 0, 3, 1, 1]
int[] count_combinations = countForCombination(combinations, orders);
// count_combinations의 max값 구하고, max값이 등장하는 idx 구하기
int[] max_index = findMaxIndex(count_combinations);
// combinations에서, max_index의 요소 값을 인덱스로 가지는 요소 -> 가능한 코스요리 조합
String[] courseMenu = findCourseMenu(combinations, max_index);
// temp에 추가
for(String courseMenuItem : courseMenu){
temp.add(courseMenuItem);
}
}
// answer array 구성
String[] answer = new String[temp.size()];
for(int i = 0; i < temp.size(); i++){
answer[i] = sortString(temp.get(i));
}
// ansewer array sort
Arrays.sort(answer);
// return
return answer;
}
// sortString
private String sortString(String str){
char[] chars = str.toCharArray();
Arrays.sort(chars);
String result = new String(chars);
return result;
}
// findCourseMenu
private String[] findCourseMenu(ArrayList<String> combinations, int[] max_index){
String[] result = new String[max_index.length];
for(int i = 0; i < max_index.length; i++){
result[i] = combinations.get(max_index[i]);
}
return result;
}
// findMaxIndex
private int[] findMaxIndex(int[] count_combinations){
ArrayList<Integer> max_index = new ArrayList<>();
int max_value = findMax(count_combinations);
// max_value가 1 이하라면 빈 배열을 리턴함
if(max_value <= 1){
int[] empty = {};
return empty;
}
for(int i = 0; i < count_combinations.length; i++){
if(count_combinations[i] == max_value)
max_index.add(i);
}
int[] result = new int[max_index.size()];
for(int i = 0; i < max_index.size(); i++){
result[i] = max_index.get(i);
}
return result;
}
// findMax
private int findMax(int[] count_combinations){
int max_value = 0;
for(int count : count_combinations){
max_value = count > max_value? count : max_value;
}
return max_value;
}
// countForCombination
private int[] countForCombination(ArrayList<String> combinations, String[] orders){
int[] count_combinations = new int[combinations.size()];
int count_idx = 0;
for(String combi : combinations){
// 조합을 손님이 주문한 횟수를 count
int count = 0;
for(String order : orders){
// 손님의 order에 combi 조합이 포함되어 있는지 확인한다
boolean ok = true;
for(int idx = 0; idx < combi.length(); idx++){
String ch = combi.substring(idx, idx + 1);
if(!order.contains(ch)){
ok = false;
break;
}
}
// 포함되어 있을 시 count++
if (ok)
count++;
}
// 조합을 주문한 횟수인 count를 저장한다
count_combinations[count_idx++] = count;
}
return count_combinations;
}
// makeMenu
private ArrayList<Character> makeMenu(String[] orders){
ArrayList<Character> menu = new ArrayList<>();
for(String order : orders){
for(int i = 0; i < order.length(); i ++){
Character x = order.charAt(i);
if(!menu.contains(x))
menu.add(x);
}
}
return menu;
}
// combination
private ArrayList<String> combination(ArrayList<Character> menu, int combi_number){
int numerator = 1;
for(int i = menu.size(); i >= menu.size() - combi_number; i--){
numerator *= i;
}
int denominator = factorial(combi_number);
int count = (int)(numerator / denominator);
boolean[] menu_visited = new boolean[menu.size()];
for(int i = 0; i < menu.size(); i++){
menu_visited[i] = false;
}
ArrayList<String> result = makeCombination(menu, combi_number, "", menu_visited, new ArrayList<String>());
return result;
}
// makeCombination
private ArrayList<String> makeCombination(ArrayList<Character> menu, int combi_number, String combi, boolean[] menu_visited, ArrayList<String> result){
if(combi_number == 0){
result.add(combi);
return result;
}
for(int i = 0; i < menu.size(); i++){
if(combi.indexOf(menu.get(i)) == -1 && !menu_visited[i]){ // combi String 내에 존재하지 않는 문자이고, 방문한 적이 없으면 추가한다
boolean[] new_menu_visited = new boolean[menu_visited.length];
for(int j = 0; j < menu_visited.length; j++){
new_menu_visited[j] = menu_visited[j];
}
new_menu_visited[i] = true;
makeCombination(menu, combi_number - 1, combi + menu.get(i), new_menu_visited, result);
}
menu_visited[i] = true;
}
return result;
}
// factorial
private int factorial(int n){
if(n == 1)
return 1;
return n * factorial(n-1);
}
}
🍵추가
-
코드가 너무 길어졌는데, 실전에서 시행착오 없이 이렇게 긴 코드를 짤 수 있을지는 잘 모르겠다.🥺 훌쩍스...
-
어딘가 개선이 필요하다는 말인데, 다른 사람들의 풀이를 보다 멋진 아이디어를 찾아냈다!
-
문제의 조건인 '각 손님의 주문에 메뉴가 중복해서 등장하지 않음' 을 이용해서 각 손님의 주문별로 조합을 만든 것이 똑똑쓰
- 나는 모든 손님이 주문한 메뉴를 먼저 구한 뒤, 그 메뉴들로 가능한 모든 조합을 구해내고 등장하지 않는 조합을 쳐내는 방식으로 했는데
- 이런 나의 방법에 비해 의심의 여지 없이 효율적. 손님 한명한명의 메뉴 주문 정보로부터 가능한 조합들을 먼저 구하기 때문.
-
HashMap, PriorityQueue등의 자료구조를 적절하게 이용한 것도 센스 있었다...
-
⭐ 위 코드를 보면서 HashMap의
getOrDefault라는 메소드를 알게 되었다 -
⭐ 어차피 오름차순으로 정렬할거라면, PriorityQueue에 담아두고 poll해서 결과를 구성하는 세련된 방법도 배웠다!
세련된 코드를 짤 수 있을 때까지 정진하자...ㅎ
코뉴의 도딩기록