[프로그래머스] 메뉴 리뉴얼

https://programmers.co.kr/learn/courses/30/lessons/72411
이문제도 다른사람의 생각을 보고 푸는법을 알게된 문제다. (아... 어렵다 코테)

완전탐색을 하면 될거라고 생각했는데, 어떻게 완탐을 돌려야 하는지 생각해내지를 못했다. 왜 못풀었을까에 대한 생각을 먼저 해보면 각각의 orders[] 에서 완탐을 돌릴 생각을 못하고, 계속 visited[] 배열을 어떻게 활용을 해서 orders[] 을 돌리면서 풀려고 했던거 같다. -근데 처음부터 느낌이 '어렵다' 긴 했음

풀이

• 핵심 아이디어

1. 각각의 orders[x] 에서 course[y] 의 값만큼 완전탐색을 돌려서 가능한 조합을 구해야 한다.
2. HashMap 에 (조합된 문자열, 발생한 횟수) 를 넣어준다. (이걸 경험해본적이 없어서 어렵게 느낀듯)
3. 만약에 orders[x+1] 에서 또 같은 문자열이 나오면 value값만 다시 조정해주면 된다.

기억할 자바 문법

• sb.deleteCharAt(sb.length()-1) : StringBuilder 에서 마지막 글자 삭제하기

• HashMap 순회 : for(String key : String map.keySet()) 을 이용하면 모든 key값들을 뽑아낼 수 있다.

import java.util.*;

class Solution {
    private static int num;
    private static StringBuilder sb = new StringBuilder();
    private static Map<String,Integer> map;
    private static int max;
    
    public String[] solution(String[] orders, int[] course) {
        String[] answer;
        List<String> result = new ArrayList<>();
        
        for(int i = 0 ; i< course.length ; i++){
            num = course[i];//뽑아야하는 개수
            map = new HashMap<>(); 
            max = 0;
            for(int j = 0 ; j< orders.length ; j++){
                String[] str = orders[j].split("");
                Arrays.sort(str);
                
                //해당 주문에서 num개만큼의 경우의 수를 모두 구한다.
                dfs(0,0,str);              
            }
            //여기서 최대로 많이 나온 조합 수 (정답) 을 넣어주자
            for(String key : map.keySet()){
                if( max > 1 && max == map.get(key)){
                    result.add(key);
                }
            }
        }
        answer = new String[result.size()];
        for(int i = 0 ; i< result.size() ; i++){
            answer[i] = result.get(i);
        }
        
        Arrays.sort(answer);
        return answer;
    }
    
    public void dfs(int start , int depth, String[] str){        
        if(depth >= num){
            String key = sb.toString();
            int value = 1;
            
            //이미 가지고 있는 조합이면 value 값 조정
            if(map.containsKey(key)){
                value = map.get(key) + 1;
            }
            
            //지금까지 나온 조합중에 가장 많이 나온 개수 갱신
            if(max < value)
                max = value;
                
            map.put(key,value);
            return;
        }
        
        for(int i = start ; i < str.length ; i++){
            sb.append(str[i]);
            dfs(i+1, depth + 1 , str);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}