[코딩테스트(Java)] 프로그래머스 72411 메뉴 리뉴얼

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

프로그래머스

 

public String[] solution(String[] orders, int[] course) {
    for (int i = 0; i < orders.length; i++) {
        StringBuilder stringBuilder = new StringBuilder();
        char[] chars = orders[i].toCharArray();
        Arrays.sort(chars);
        stringBuilder.append(chars);
        orders[i] = stringBuilder.toString();
    }

    List<String> results = new ArrayList<>();
    // 코스 길이에 따라 조합 생성
    for (int cutSize : course) {
        Map<String, Integer> orderCount = new HashMap<>();
        int max;

        // 각 주문에서 조합 생성 (백트래킹)
        for (String order : orders) {
            if (order.length() >= cutSize) {
                backtracking(order, "", 0, cutSize, orderCount);
            }
        }

        // 최대 빈도 기반 결과 추가
        max = orderCount.values().stream().max(Integer::compareTo).orElse(0);
        if (max >= 2) {
            for (Map.Entry<String, Integer> entry : orderCount.entrySet()) {
                if (entry.getValue() == max) {
                    results.add(entry.getKey());
                }
            }
        }
        System.out.println(orderCount);
    }
    // 사전순 정렬 후 반환
    Collections.sort(results);
    return results.toArray(new String[0]);
}

private void backtracking(String order, String now, int index, int cutSize, Map<String, Integer> orderCount) {
    if (now.length() == cutSize) {
        orderCount.put(now, orderCount.getOrDefault(now, 0) + 1);
        return;
    }

    for (int i = index; i < order.length(); i++) {
        backtracking(order, now + order.charAt(i), i + 1, cutSize, orderCount);
    }
}

 

 

 

📍포인트

1. 정렬까지는 하는 게 맞음. (map 특징상 AB, BA를 다르게 보는데 이러면 안 되기 때문에)
2. 코스 길이에 따른 조합 생성 (for문) 도 맞음
3. 각 주문 조합 생성 (for문) 도 맞음 → 이 단계에서 길이가 course의 각 요소보다 짧은지 판별
4. 백트래킹으로 로직을 진행시킴 → map에 모든 경우와 개수가 잘 쌓임
5. 최대 빈도를 가지면서 2번 이상 등장하고 최대값을 만족하는 조합만 반환 배열에 추가

 

 

 

📍삽질

1. 문제 이해는 빠르게 한 것 같은데 구현 단계에서 많이 힘들었다.
2. 완탐으로 접근하다가 점차 증가하는 for문 때문에 포기했다. 하지만 최대 course가 10까지 이므로 10중 for문을 쓰면 풀 수 있긴 하다.
3. 백트래킹 재귀를 이해하는데 상당한 시간이 걸렸다. 앞으로 이걸 어떻게 응용하지?