2021_KAKAO_BLIND_RECUITMENT_메뉴리뉴얼_HASHMAP

https://programmers.co.kr/learn/courses/30/lessons/72411

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

오늘은 오랜만에 카카오 코딩테스트 문제를 풀어보았다. 항상 Eclipse와 같은 IDE로 코드를 쳐보다가 프로그래머스로 제출할 때는 항상 낯선 기분이 든다. 정말 세세하게 어떤것은 괄호를 붙이는지, 함수의 대소문자는 어떤지에 대해 많은 회고의 시간을 갖게 한다. 나중에 간단한 손코딩 문제도 많이 푼다고 하던데,, 종종 연습을 시작해야 겠다는 생각이 들었다. 이런저런 알고리즘을 많이 배우고 학습하다 보면 문제를 풀이할 때 다양한 길을 찾을 수 있을 줄 알았다. 필자가 아직 개념을 제대로 정리하지 않아서 그런지 문제를 풀기 전에 머리로만 이렇게 해볼까 저렇게 해볼까 고민만 하다보니 오히려 더 복잡해진 기분이다. 천천히 차분하게 정리하면서 학습을 이어나가자. 

필자는 해당 문제를 풀이하기 전에 모든 조합의 경우의 수를 구해볼까? 하다가 너무 시간이 오래걸릴 것 같아서 생각을 바꾸어 최장 공통 부분 수열LCS로 풀어볼까 했는데, 여러 개의 배열을 비교하는 방법이 떠올리기 쉽지도 않았고, 비효율적이다. 한참을 돌고 돌아 결국 재귀를 사용해 조합을 다 구해보기로 했다.

[ 문제 분석 & 풀이 ]

• 손님이 주문한 단품 메뉴들을 요소로 갖는 문자열 배열과, 코스 요리를 구성할 단품 메뉴의 개수가 저장된 정수형 배열이 인자값으로 주어진다. 
• 조합을 짜는 기준은 적어도 2회 이상 주문이 되었어야 하고, 적어도 2명 이상의 사람이 해당 조합으로 주문을 했어야 한다. 
• 문제에서 주어진 정수형 배열의 값을 사용해 조합의 길이(재귀의 깊이)를 정할 수 있다.
• 모든 문자열 배열에 대해 재귀를 통해 구한 조합을 포함하는지 확인한다. 
• 해당 조합에 대한 빈도수를 map의 value로 저장한다. 
• map에 저장된 value중에서 최댓값을 구하고, 다시 반복으로 탐색을 하면서 최댓값과 동일한 빈도수로 주문을 받은 조합을 결과 배열에 추가한다. 
• 결과배열을 정렬해서 제출한다. 

 

1. [ 정렬 및 조합 구하기 ]

정수형 배열은 오름차순으로 구성이 되어 있다고 문제에서 주어졌다. 추가로 조합을 담은 문자열 배열로 정렬을 하라고 했으니 가장 먼저 입력값으로 들어오는 문자열 배열을 정렬을 해주고 조합을 구하기 시작한다. 

1. 입력으로 주어진 문자열 배열의 각 요소를 문자 배열로 바꾸어서 정렬을 진행하고, 다시 문자열로 바꾸어서 저장한다.
2. 개선 루프를 쓰긴 했지만 단순한 구조이다. 어차피 정수형 배열 course는 오름차순 정렬된 상태이다. 코스요리의 개수 혹은 길이(courseCnt)가 주어질 때, 이 개수에 맞도록 조합을 구할 건데, 재귀를 통해서 한 문자씩 추가하면서 구해줄 것이다. 빈 문자열과 조합을 뽑을 기준 문자열, 그리고 구해야할 조합의 길이를 인자로 넘겨준다. 
3. 기준 문자열 order에서 한 글자씩 떼어서 빈문자열 ans_list에 넣는다. 이때, 문자가 하나 추가될 때마다 count를 1씩 줄여서 재귀의 깊이를 관리하고, count==0이라는 것은 필요한 길이만큼 조합이 구해졌다는 의미이므로 basecase를 작성해 해당 조합에 대한 빈도수를 누적하고 탈출한다.

import java.util.*;
class Solution {
    public String[] solution(String[] orders, int[] course) {     
        //문자열 배열 -> 문자 배열 + 정렬
        for(int i=0; i<orders.length; i++){
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = String.valueOf(arr);
        }
        
        //orders배열에서 주문이 들어온 단품메뉴의 조합의 경우의 수를 본다.(범위가 엄청 크지 x)    
        for(int courseCnt : course){//코스 요리를 구성할 단품 메뉴의 개수
            for(String order : orders){
                combi("",order, courseCnt);
            }//end-for-order    
        }//end-for-course 
    }
 
    //                조합의 결과    조합을 뽑을 문자열  조합할 문자열의 개수
    public void combi(String ans_list, String order, int count){
        if(count == 0){
            food.put(ans_list, food.getOrDefault(ans_list, 0) + 1);
            return;
        }
        //0~order.length까지 탐색하면서 조합하기 
        for(int i=0; i<order.length(); i++){
            combi(ans_list+order.charAt(i), order.substring(i+1), count-1);
        }
    }
}
 

 

2. [ 구한 조합중에서 빈도수가 최대인 모든 경우의 수를 결과 배열에 추가한다. ]

1. 해당 courseCnt에 대해 모든 orders 문자열을 탐색했다면(모든 조합을 다 구했다면) 비교를 시작한다.
2. 현재 map(food)에 저장된 value값(주문 빈도수)을 리스트로 만든다. -> 컬렉션의 오버로드 된 생성자를 응용
3. 내장함수를 사용해서 빈도수 중 최대값을 구한다. 
4. 각 키에 해당 하는 value가 최댓값과 동일하다면 그 key값을 결과 리스트에 add한다. 
5.  다음 길이에 대한 조합을 또 구해야 하기 때문에 food맵을 초기화 시킨다. 
6. 결과 리스트에 있는 요소들을 정렬 시키고 실제로 제출할 answer[]배열에 값을 하나씩 넣어준다.

import java.util.*;
class Solution {
    static Map<String, Integer> food = new HashMap<>();
    static List<String>           answerList = new ArrayList<>();
    public String[] solution(String[] orders, int[] course) {
        for(int courseCnt : course){//코스 요리를 구성할 단품 메뉴의 개수
            for(String order : orders){
                combi("",order, courseCnt);
            }//end-for-order
            
 
            if(!food.isEmpty()){//적어도 하나의 조합이 완성되어 맵에 있다면 실행
                //맵의 value값을 리스트 형태로 반환받는데, 그대로 리스트 생성
                List<Integer> ans = new ArrayList<>(food.values());
                //최댓값 -> 각 조합에 대해 가장 많이 주문 받은 크기를 구한다.
                int max = Collections.max(ans);
                
                if(max > 1){//적어도 2번 이상은 주문이 들어왔어야 함
                    for(String key : food.keySet()){
                        if(food.get(key) == max){
                            //최대값이라면 모두 결과 리스트에 추가하기 
                            answerList.add(key);
                        }
                    }
                }
                
                food.clear();
            }
            
        }//end-for-course
        
        Collections.sort(answerList);
        String[] answer = new String[answerList.size()];
        for(int i=0; i<answer.length; i++){
            answer[i] = answerList.get(i);
        }
    
        return answer;
    }
}
 

 

3. [ 전체 소스코드 ]

import java.util.*;
class Solution {
    static Map<String, Integer> food = new HashMap<>();
    static List<String>           answerList = new ArrayList<>();
    public String[] solution(String[] orders, int[] course) {
        
        
        
        //문자열 배열 -> 문자 배열 + 정렬
        for(int i=0; i<orders.length; i++){
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = String.valueOf(arr);
        }
        
        //orders배열에서 주문이 들어온 단품메뉴의 조합의 경우의 수를 본다.(범위가 엄청 크지 x)    
        for(int courseCnt : course){//코스 요리를 구성할 단품 메뉴의 개수
            for(String order : orders){
                combi("",order, courseCnt);
            }//end-for-order
            
            if(!food.isEmpty()){//적어도 하나의 조합이 완성되어 맵에 있다면 실행
                //맵의 value값을 리스트 형태로 반환받는데, 그대로 리스트 생성
                List<Integer> ans = new ArrayList<>(food.values());
                //최댓값 -> 각 조합에 대해 가장 많이 주문 받은 크기를 구한다.
                int max = Collections.max(ans);
                
                if(max > 1){//적어도 2번 이상은 주문이 들어왔어야 함
                    for(String key : food.keySet()){
                        if(food.get(key) == max){
                            //최대값이라면 모두 결과 리스트에 추가하기 
                            answerList.add(key);
                        }
                    }
                }
                
                food.clear();
            }
            
        }//end-for-course
        
        Collections.sort(answerList);
        String[] answer = new String[answerList.size()];
        for(int i=0; i<answer.length; i++){
            answer[i] = answerList.get(i);
        }
        
        
        return answer;
        //가장 많이 함께 주문한 단품메뉴로 코스 요리를 구성한다.(최소 2가지 이상의 단품 메뉴 + 단품메뉴를 주문한 주문자가 최소 2명 이상)
        
    }
    //                조합의 결과    조합을 뽑을 문자열  조합할 문자열의 개수
    public void combi(String ans_list, String order, int count){
        if(count == 0){
            food.put(ans_list, food.getOrDefault(ans_list, 0) + 1);
            return;
        }
        
        //0~order.length까지 탐색하면서 조합하기 
        for(int i=0; i<order.length(); i++){
            combi(ans_list+order.charAt(i), order.substring(i+1), count-1);
        }
    }
    
}