프로그래머스 (카카오) | LV.2 메뉴 리뉴얼 - DFS (Java)

⬛ 프로그래머스 (카카오) | LV.2 메뉴 리뉴얼 - DFS (Java)

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

프로그래머스

문제설명

---

💚문제 접근 방식

내 생각으로는 각 orders의 문자열에 대해서 course 개수만큼 nCr 조합을 구성해서 그 구성의 개수를 Map으로 카운팅하면서 구현하면 될 거라고 생각했다.

char[] 배열로 매번 lv 깊이의 인덱스에 선택한 문자를 담도록 구성했는데, 중복없이 구현하기 위해 start 인덱스도 매번 DFS에 주도록하여 중복되지 않은 선택을 하도록 했다.

 

1) orders[] 주문으로 들어온 애들이 정렬된 애들은 아니다. 얘를 대상으로 DFS탐색을 할거라 문자열도 정렬 시킨다.

2) course는 선택한 메뉴 조합인데, 나의 경우 course[i] 값보다 menu길이가 작다면 nCr 불가능하기 때문에 continue 해주고 그 외의 경우에는 DFS 탐색을 시도했다.

//그니까 해당 문자열에 대해 course 개수만큼 깊이 조합을 구성하는 것

3) DFS를 탐색

• lv이 타겟lv과 같아지면 sorting 후 map에 담는다.
• 그 외의 경우 start 인덱스부터 방문 전인 문자에 대해 문자열을 구성해주며 다음 깊이로 간다.

4) 모든 DFS탐색을 마친 상태에서는 각 orders 메뉴로 구성할 수 있는 course 조합을 카운팅한 map이 생성된 상태이다.

5) 이 상태에서 map에 구성된 counting이 가장 많은 maxCount를 찾고, 주문이 2개 이상이면서 maxCount와 같은 애들에 대해 List에 담아 오름차순 정렬 후 반환하면 된다.

💚 제출 코드

import java.util.*;
class Solution {
    //얘네 두개는 구성 길이 정해지면 초기화해서 DFS 호출
    static char[] arrChar;
    static boolean[] visited;
    //얜 완전 전체 공유 
    static Map<String, Integer> map;
    //DFS
    static void DFS(String str, int lv, int targetLv, int st){
        if(lv == targetLv){
            Arrays.sort(arrChar);
            map.put(String.valueOf(arrChar), map.getOrDefault(String.valueOf(arrChar), 0) + 1);
            return;
        }
        
        for(int i=st; i<str.length(); i++){
            if(!visited[i]){
                visited[i] = true;
                arrChar[lv] = str.charAt(i);
                DFS(str, lv+1, targetLv, i+1);
                visited[i] = false;
            }
        }
    }
    
    // 솔루션 함수
    public String[] solution(String[] orders, int[] course) {
        List<String> answerList = new ArrayList<>(); // 정답을 저장할 리스트 생성
        int idx= 0;
        for(String x : orders){
            char[] tmp = x.toCharArray();
            Arrays.sort(tmp);
            orders[idx++] = String.valueOf(tmp);
        }
        
        for (int x : course) { 
            map = new HashMap<>(); 
            int maxCount = 0;
 
            // 모든 주문 메뉴에 대해 DFS를 통해 조합
            for (String menu : orders) {
                if (menu.length() < x) continue; // 메뉴 길이가 x보다 작으면 건너뜀
                arrChar = new char[x];
                visited = new boolean[menu.length()];
                DFS(menu, 0, x, 0);
            }
            
            for(String key : map.keySet()) {
                maxCount = Math.max(maxCount, map.get(key));
            }
            
            for(String key : map.keySet()){
                if(map.get(key) >= 2 && maxCount == map.get(key)){
                    answerList.add(key);
                }
            }
        }

        String[] answer = new String[answerList.size()];
        answerList.toArray(answer);
        Arrays.sort(answer); 
        return answer;
    }
}