프로그래머스 - 메뉴 리뉴얼

2021 카카오 블라인드 테스트 문제다. Map자료구조와 조합을 통해서 접근한다.

1. 코스에 들어갈 음식의 숫자별로 반복문을 실행한다.
2. 손님의 주문 목록별로 사전순 정렬된 메뉴 조합을 만들고 개수를 카운팅한다.
3. 2에서 카운팅한 메뉴 조합 중 가장 많이 카운트된 조합들을 answer 목록에 추가한다.
4. 다시한번 answer 목록을 정렬한다.

import java.util.*;

class Solution {
    
    // 조합을 저장할 hashMap
    Map<String, Integer> map = new HashMap<>();
    
    // answer를 저장할 리스트
    ArrayList<String> answerList = new ArrayList<>();
    
    public String[] solution(String[] orders, int[] course) {    
    	// course에 사용될 음식의 개수별로 반복문을 실행합니다.
        for(int i = 0 ; i<course.length; i++){
        	
            // 주문 목록만큼 반복문을 실행합니다.
            for(int j = 0 ; j<orders.length; j++){
                String foods = orders[j];
                // 각 음식별로 조합 실행
                combi(course[i], 0, 0, foods, new StringBuilder());
            }
            // 최대값 변수 선언
            int max = 0;
            // map의 value들 중 가장 큰 값을 찾아줍니다.
            for(Integer value : map.values()){
                max = Math.max(max, value);
            }
            
            // 문제의 조건인 코스로 포함된 횟수의 최대값이 2번 이상인 경우
            if(max>=2){
            	// value가 최대값인 key들을 answer 목록에 추가해줍니다.
                for( String key : map.keySet() ){
                    if(map.get(key) == max){
                        answerList.add(key);
                    }
                }
            }
            
            // 다음 코스요리 조합을 실행하기 전에 map을 비워줍니다.
            map.clear();
        }
        // 사전순 정렬
        Collections.sort(answerList);      
        // List를 array로 변경해 리턴합니다.
        return answerList.toArray(new String[answerList.size()]);
    }
    
    /* 
    	end = 코스의 길이(메뉴의 개수), depth = 추가된 메뉴의 개수, sIndex = 조합이 시작될 인덱스
        foods = 조합에 사용될 주문 목록, course = 조합을 저장할 변수
    */
    public void combi( int end, int depth, int sIndex, String foods, StringBuilder course ){
    	// 메뉴가 코스의 정해진 길이만큼 추가 됐다면 종료
        if(depth == end){
        	// 정렬을 위한 charArray변환
            char[] arr = course.toString().toCharArray();
            // 사전순 정렬
            Arrays.sort( arr );
            // String으로 변환한 뒤 map에 추가
            String result = String.valueOf(arr);
            map.put(result, map.getOrDefault(result, 0)+1);
        }
        
        // 조합
        for(int i = sIndex; i<foods.length(); i++){
            combi(end, depth+1, i+1, foods, course.append(foods.charAt(i)));
            course.deleteCharAt(course.length()-1);
        }
    }
}

String의 불변 속성 때문에 StringBuilder를 써줘야 훨씬 효율적이다. 첫 제출에선 귀찮다는 이유로 String과 + 연산자를 썼다가 3점을 받아버렸다.. 해당 제출에서는 평균 실행 시간이 25ms정도에 느린 경우 50ms도 초과했으나, StringBuilder로 변환한 뒤에는 평균 10ms 내외로 크게 줄었다. 점수도 18점으로 상승한 건 덤.

오늘의 교훈

귀찮아도 지킬 건 지키자.