[알고리즘] 프로그래머스 메뉴 리뉴얼 (2021 KAKAO BLIND RECRUITMENT) -DFS- 자바 (2개 시간초과)

 

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

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

 

 

 

 

프로그래머스 메뉴리뉴얼 문제를 풀어봤습니다. ㅎㅎ

 

풀다가 테스트케이스 18,20이 시간초과가 뜨고 나머진 다 통과했는데 원인을 찾지 못하고 있습니다. ㅠ 효율성검사도 아닌 정확도 검산데 뭐가 문젠건지 잘 모르겠네요..

통과는 못하였지만 다른 할일도 있어 일단 제가 풀이한 코드를 포스팅하려고 합니다.

이후에 코드를 좀 더 효율적으로 짤게 있을지 생각해봐야겠습니다. 틀린원인을 아시는분은 댓글 달아주시면 감사하겠습니다!! ㅎㅅㅎ 프로그래머스 질문하기에서도 없더라고요 ㅠ

 

문제 접근은 DFS와 MAP을 사용해야겠다 생각했습니다. 생각대로 DFS로 모든 메뉴 경우의 수를 조합 및 탐색하고 조건에 맞는 메뉴와 해당 메뉴를 고른 개수를 MAP에 저장했습니다.  

그다음 MAP을 반복문을 돌려 2개 이상 골라진 메뉴 중 가장 많이 선택된 메뉴를 리스트에 담고 정렬했습니다.

 

주석에 풀이를 적어놨습니다.

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.*;

class Solution {
    private Map<String, Integer> map = new HashMap<>();
    private Set<String> set = new HashSet<>();
    private boolean[] isVisited;

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new String[]{"ABCD", "ABCD", "ABCD"}, new int[]{2, 3, 4});
    }

    public String[] solution(String[] orders, int[] courses) {
        for (String order : orders) { //각 요리 탐색 및 조합
            for (int course : courses) { // 초기화 및 탐색
                isVisited = new boolean[order.length()];
                set = new HashSet<>();
                dfs("", order, course, isVisited);
            }
        }
        int max = 2; //최소 2개이상은 주문되었어야함
        List<String> resultList = new ArrayList<>(); // 최종 메뉴 담을 리스트 (답)
        List<String> tmpList = new ArrayList<>(); //코스 별 메뉴 담을 리스트 -> 각 코스별 메뉴들을 resultList 에 추가할거임
        for (int course : courses) {
            for (String key : map.keySet()) {
                if (course == key.length()) { // 해당 코스개수인 경우
                    if (map.get(key) >= max) {
                        if (map.get(key) == max) { // 최대 메뉴 개수와 같다면 그냥 추가
                            tmpList.add(key);
                        } else { //최대 메뉴 개수보다 더 큰게 나왔다면 리스트 클리어 후 추가
                            tmpList.clear();
                            tmpList.add(key);
                        }
                        max = map.get(key);
                    }
                }
            }
            //최종 메뉴리스트(답)에 추가
            resultList.addAll(tmpList);
            //초기화
            tmpList.clear();
            max = 2;
        }
        //메뉴 정렬 후 정답 리턴
        Collections.sort(resultList);
        String[] answer = new String[resultList.size()];
        for (int i=0; i<resultList.size(); i++){
            answer[i] = resultList.get(i);
        }
        return answer;
    }

    private void dfs(String str, String order, int course, boolean[] isVisited) {
        if (str.length() == course) { //코스길이에 해당하는 메뉴만 조합 가능
            char[] c = str.toCharArray();
            Arrays.sort(c); //정렬해줘야함
            String menu = new String(c); // char배열 -> String으로 변환
            if (!set.contains(menu)) { // 해당 메뉴 추가한적 없으면 추가 (중복방지)
                map.put(menu, map.getOrDefault(menu, 0) + 1); // 맵에 메뉴이름(key)과 개수(value) 추가
                set.add(menu);
            }
            return;
        }
        for (int i = 0; i < order.length(); i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                dfs(str + order.charAt(i), order, course, isVisited);
                isVisited[i] = false;
            }
        }
    }
}

https://github.com/mtjin/algorithm_practice/commit/edb674060004639b97927a45b8255ec867e41e33

프로그래머스 메뉴 리뉴얼 풀이 · mtjin/algorithm_practice@edb6740

 

 

[2021-07-07 재도전]

비효율적인 부분을 제거를했지만 똑같이 2개 실패가뜹니다 ㅠ

import java.util.*;

class Solution {
    private static Map<String, Integer> map = new HashMap<>();
    private static List<String> orderList = new ArrayList<>();
    private static int max = 2; // 최소 2개이상은 주문되었어야함
    private static List<String> resultList = new ArrayList<>(); // 최종 메뉴 담을 리스트 (답)
    private static Set<String> set = new HashSet<>();
    private static boolean[] isVisited;

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new String[]{"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"}, new int[]{2, 3, 4});
    }

    private static void dfs(String str, String order, int course, boolean[] isVisited) {
        if (str.length() == course) { //코스길이에 해당하는 메뉴만 조합 가능 + 그 이상 탐색필요 X
            char[] c = str.toCharArray();
            Arrays.sort(c); //정렬해줘야함
            String menu = new String(c); // char배열 -> String으로 변환
            if (!set.contains(menu)) { // 해당 메뉴 추가한적 없으면 추가 (중복방지)
                map.put(menu, map.getOrDefault(menu, 0) + 1); // 맵에 메뉴이름(key)과 개수(value) 추가
                max = Math.max(max, map.get(menu));
                if (map.get(menu) >= max) {
                    if (map.get(menu) == max && !orderList.contains(menu)) { // 같은개수 더 있는경우 + 추가안한메뉴인 경우
                        orderList.add(menu);
                    } else { // 더 큰개수인 경우
                        orderList.clear();
                        orderList.add(menu);
                    }
                }
                set.add(menu);
            }
            return;
        }
        for (int i = 0; i < order.length(); i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                dfs(str + order.charAt(i), order, course, isVisited);
                isVisited[i] = false;
            }
        }
    }

    public String[] solution(String[] orders, int[] courses) {
        for (int course : courses) { //각 요리 탐색 및 조합
            //초기화
            map.clear();
            orderList.clear();
            max = 2;
            for (String order : orders) {
                set.clear();
                isVisited = new boolean[order.length()];
                dfs("", order, course, isVisited);
            }
            resultList.addAll(orderList);
        }
        //메뉴 정렬 후 정답 리턴
        Collections.sort(resultList);
        String[] answer = new String[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            answer[i] = resultList.get(i);
        }
        return answer;
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!