[Algorithm] Programmers_메뉴 리뉴얼 in Java

💡 Programmers Lv2. 메뉴 리뉴얼:

2개 이상의 메뉴 조합에서 가장 많이 나온 메뉴들의 조합으로 코스요리 만들기

🌱 코드 in Java

알고리즘: Priority Queue

import java.util.*;

class Solution {
    public static Map<String, Integer> menu = new HashMap<>();
    
    public String[] solution(String[] orders, int[] course) {
        List<String> answer = new ArrayList<>();
        
        for (int i = 0; i < orders.length; i++) {
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr); // AB, BA를 같은 조합으로 보기 위해 각 order 정렬
            orders[i] = String.valueOf(arr);
        }
    
        for (int len : course) { // 메뉴 길이별로 조합 만들기
            for (String order : orders) // 백트레킹으로 각 order별 조합 생성
                comb(order, "", 0, len);
            int max = 0;
            if (!menu.isEmpty())
                max = Collections.max(menu.values()); // 해당 길이에서 가장 많이 나온 메뉴 찾기
            if (max < 2) // 최소 2명 이상의 손님으로부터 주문된 조합만 가능하여 넣은 조건
                continue;
            for (Map.Entry<String, Integer> entry : menu.entrySet()) {
                if (entry.getValue() == max) // 가장 많이 나온 조합이 많을 경우 다 만들기
                    answer.add(entry.getKey());
            }
            menu.clear(); // 해당 길이 끝나면 map clear
        }
        
        return answer.stream().sorted().toArray(String[]::new); // 메뉴 전체 정렬
    }
    
    public static void comb(String order, String s, int start, int len) { // 조합 백트래킹
        if (len == 0) {
            menu.put(s, menu.getOrDefault(s, 0) + 1);
            return;
        }
        for (int i = start; i < order.length(); i++) {
            comb(order, s + order.charAt(i), i + 1, len - 1);
        }
    }
}

이번 문제는 하.. 문제를 잘 읽자!!를 여실히 느꼈던 그런 문제였다.
빼먹은 조건들 때문에 내가 몇번을 다시 풀었는지?

여기서 중요한 건

1. 최소 2번 이상 나온 조합만 코스로 등극 가능
2. 같은 길이의 조합이 여러개라면 그 중 가장 많이 나온 조합만 코스로 등극 가능
3. course로 들어온 길이의 조합만 생성
4. 각 order의 메뉴 구성은 정렬되어있지 않다.
5. 모든 코스는 길이와 상관없이 알파베티컬하게 정렬되어야 한다.

여기서 몇가지 조건을 빼먹어서 처음엔 트리맵으로 했다가...
다시 걍 맵으로 바꾼다음에 마지막에 order 정렬하는 식으로 바꿨다...

진짜로 문제를 잘보자.

이번 문제는 여러 조합을 만드는 문제였어서 백트래킹을 떠올리기 쉬웠다.

🧠 기억하자

1. map.entrySet()

• 맵의 전체 자료를 확인할 수 있다.
• Map.entry<> 자료형으로 꺼내서 쓸 수 있음
• 꺼낸 entry는 entry.getKey()와 같이 불러쓸 수 있음
• map.keySet()은 key만 불러다 쓸 수 있음

2. 스트링 문자열을 정렬하고 싶을 땐 배열로 바꾸자

• 스트링 그 자체를 정렬할 순 없다.
• 하지만 배열은 가능하지
• char[] arr = string.toCharArray() -> Arrays.sort(arr) -> String str = String.valueOf(arr);
• 스트링의 인덱스로 접근하고 싶으면 str.charAt(idx)
• 스트링의 길이를 알고 싶으면 str.length가 아닌 str.length()