관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/DFS, BFS, 시뮬, 백트래킹

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

막무가내막내 2021. 7. 6. 22:01
728x90

 

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

 

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

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서

programmers.co.kr

 

 

 

 

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

 

풀다가 테스트케이스 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

Permalink This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. Showing 1 changed file with 72 additions and 0 deletions. +72 −0 프로그래머스 메뉴 리뉴얼 (2021 KAKAO BLIND RECRUITMENT

github.com

 

 

[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;
    }
}

 

 

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

 

 

728x90
Comments