프로그래머스: 메뉴 리뉴얼 (Java)

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

프로그래머스

 

 

 

 

 

 

 

 

---

 

그렇게 어려운 문제는 아닌데, 독해력 문제로 많이 헤맸습니다.

 

헤맨 부분

'입출력 예 #2'에서 왜 "AB"는 정답이 아닐까? -> 길이가 같은 course에 대해서는 등장횟수가 가장 많은 메뉴만 코스메뉴 요리 후보군에 넣기 때문입니다.

아마 "... 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다."가 저 logic이지 않나 싶은데, 알고 읽어도 잘 모르겠네요ㅎㅎ;;

 

풀이

풀이 1 (내 풀이): 메뉴 길이별로 가능한지 확인

음식을 길이가 26인 이진수로 보아, 'i(0-based)번째 알파벳이 어떤 사람이 먹은 음식에 포함된다' <=> '(1<<i)번째 자리가 1'로 저장했습니다. 이후, 코스요리의 가능한 길이에 대해 가능한 모든 음식 조합을 조합으로 구하여, 이 음식을 모두 먹은 사람의 수가 가장 많은 것만 코스요리 후보군에 넣었습니다. 이후, 이진수를 다시 문자열로 바꾸어 정렬한 후 정답을 출력했습니다.

 

풀이 2: 바킹독님 풀이

각 사람이 먹은 음식의 수는 10 이하이므로, 한 사람이 먹은 음식에 모두 해당되는 메뉴는 최대 2^10 - 1개입니다. 그리고 order가 20 이하이므로, 이렇게 후보군을 모두 처리하면 20 * (2^10 - 1) 개의 후보군이 각 길이별로 몇 번 나왔는지를 확인할 수 있습니다.

 

풀이 비교

당연히 풀이 2가 더 좋습니다. 비교해보면, 풀이 2가 10배정도 더 빠르고, 코드도 더 간결합니다. 다만, 풀이 1을 짜면서 '연산횟수가 최대 sigma(26Ci) where 1 <= i <= 10'이고, 이는 넉넉하게 3천만 이하여서 시간 제한에 아마 안 걸릴거다'를 인지하고 짰기에 큰 문제는 없는 듯합니다.

 

 

배운 점

카카오 코테는 자유로운 환경에서 보므로, 암기가 잘 안되는 library 사용을 적극적으로 할 필요가 있습니다. 그러려면 '뭐가 있는지는 알아야' 할 거 같습니다.

구체적으로,

 - List 내 HashMap 담아서 사용하기

 - toCharArray()

 - list.toArray(new String[길이]), 길이 == 0으로 넣으면 딱 맞는 길이의 String 배열로 변환

을 배웠습니다.

 

 

코드

풀이 1

import java.util.*;
 
class Solution {
 
    static String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    static Set<Integer> set = new HashSet<>();
    static Set<Integer> tempSet = new HashSet<>();
    static int tempMax = 0;
    static int[] ordersBit;
 
    public String[] solution(String[] orders, int[] course) {
        ordersBit = new int[orders.length];
        for (int i = 0; i < orders.length; i++) {
            for (int j = 0; j < orders[i].length(); j++) {
                ordersBit[i] += (1<<(orders[i].charAt(j)-'A'));
            }
        }
 
        for (int c: course) {
            tempMax = 2;
            tempSet.clear();
            dfs(0, 0, 0, c);
            for (int food: tempSet) {
                set.add(food);
            }
        }
 
        List<String> list = new ArrayList<>();
        String[] answer = new String[set.size()];
        for (Integer food: set) {
            list.add(intToStr(food));
        }
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
 
    static void dfs(int cnt, int idx, int cur, int course) {
        if (cnt == course) {
            int temp = 0;
            for (int order: ordersBit) {
                if ((order & cur) == cur) {
                    temp++;
                }
                if (temp > tempMax) {
                    tempMax = temp;
                    tempSet.clear();
                    tempSet.add(cur);
                }
                else if (temp == tempMax) {
                    tempSet.add(cur);
                }
            }
            return;
        }
 
        for (int i = idx; i < 26; i++) {
            dfs(cnt+1, i+1, cur | (1<<i), course);
        }
    }
 
 
    static String intToStr(int food) {
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        while (food > 0) {
            if (food % 2 == 1) sb.append(alphabet.charAt(idx));
            idx++;
            food /= 2;
        }
        return sb.toString();
    }
}

 

 

풀이 2

import java.util.*;
 
class Solution {
    public String[] solution(String[] orders, int[] course) {
        // 0. freq의 i번째 index에 '길이가 i인 메뉴들의 등장 빈도'를 저장
        List<HashMap<String, Integer>> freq = new ArrayList<HashMap<String, Integer>>();
        for (int i = 0; i < 11; i++) {
            freq.add(new HashMap<>());
        }
 
        // 1. 가능한 메뉴 조합을 모두 넣기
        for (String order: orders) {
            int len = order.length();
            for (int i = 1; i < (1 << len); i++) {
                char[] food = order.toCharArray();
                Arrays.sort(food);
                int temp = i;
                String menu = "";
                for (int j = 0; j < len; j++) {
                    if ((temp & 1) == 1) menu += food[j];
                    temp /= 2;
                }
                freq.get(menu.length()).put(menu, freq.get(menu.length()).getOrDefault(menu, 0) + 1);
            }
        }
 
        // 2. 각 길이별로 최대 등장을 찾고, 넣어줌
        List<String> list = new ArrayList<>();
        for (int len: course) {
            int maxFreq = 2;
            Set<String> tempSet = new HashSet<>();
            for (String key: freq.get(len).keySet()) {
                int tempFreq = freq.get(len).get(key);
                if (tempFreq == maxFreq) {
                    tempSet.add(key);
                } else if (tempFreq > maxFreq) {
                    tempSet.clear();
                    maxFreq = tempFreq;
                    tempSet.add(key);
                }
            }
 
            for (String menu: tempSet) {
                list.add(menu);
            }
        }
 
        Collections.sort(list);
        return list.toArray(new String[0]);
    }
}