[프로그래머스 Level2] 메뉴 리뉴얼(JAVA) - 2021 카카오

[문제]

https://programmers.co.kr/learn/courses/30/lessons/72411?language=java 

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

해당 문제의 내용이 길어 생략했습니다.

---

[문제 풀기 전]

 

카카오 문제는 항상 문제를 잘 읽는것은 기본이고, 2레벨 정도 난이도는 어설프게 자료구조를 알고있으면 풀 수 없는 것 같다. 문제가 길 뿐이지 생각보다 구현한 코드를 보면 그렇게 길지도 않고 엄청 어렵다 느낌은 들지 않는다. HashMap 에 대하여 좀 더 정확한 개념과 메서드를 익숙하게 다루는게 중요한 것 같다.

 

---

[문제 풀이]

 

각 메뉴별로 만들 수 있는 조합을 만들면 된다. 선택하고 안하고의 방식을 사용할 것인데 왜냐하면 순서와 상관없이 결과는 같기 때문입니다.(XY = YX ) 그런데 이 문제에서 결과를 오름차순 형태로 배열에 담겨있어야하니 정렬을 미리 해두면 편하게 코드를 구현할 수 있습니다.

 

course 배열에 담긴 수 만큼 코스요리를 만들어야 하니 각각 요소의 개수가 되면 탈출하도록 dfs를 구현 할 것입니다.

그래서 course의 수만큼 반복을 해야하고 HashMap<요리조합, 주문된 수> 의 형태로 보관을 할 것입니다.

해당 HashMap이 완성이 되었으면 이 해시맵이 비어있지 않다면 max값을 찾을 건데 이 값을 찾기 쉽게 List에 옮겨 Collections.max 를 활용하여 max값을 찾으면 됩니다. 그리고 2개이상 주문 되어야 코스요리가 되기 때문에 max > 1 의 조건을 담고 중복이 허용되니 max 값이랑 일치하는 모든 키를 정렬한 뒤 배열에 담으면 됩니다. 

 

---

[소스 코드]

 

import java.util.*;

class Solution {
    
    static HashMap<String, Integer> hm = new HashMap<>();
    static ArrayList<String> answerList = new ArrayList<>();
    
    public String[] solution(String[] orders, int[] course) {
        String[] answer = {};

        for (int i : course) {
            for (String order : orders) {
                char[] chars = order.toCharArray();
                Arrays.sort(chars);

                dfs(0, "", chars, i);
            }

            if (!hm.isEmpty()) {
                List<Integer> countList = new ArrayList<>(hm.values());
                int max = Collections.max(countList);

                if (max > 1) {
                    for (String key : hm.keySet()) {
                        if (hm.get(key) == max) {
                            answerList.add(key);
                        }
                    }
                }
            }
            hm.clear();
        }

        Collections.sort(answerList);
        answer = new String[answerList.size()];

        for (int i = 0; i < answer.length; i++) {
            answer[i] = answerList.get(i);
        }

        return answer;
    }

    static void dfs(int depth, String course, char[] chars, int i) {
        if (course.length() == i) {
            if (hm.containsKey(course)) {
                hm.put(course, hm.get(course) + 1);
            }else{
                hm.put(course, 1);
            }
            return;
        }

        if (depth >= chars.length) {
            return;
        }

        dfs(depth + 1, course + chars[depth], chars, i);
        dfs(depth + 1, course, chars, i);
    }
}