[프로그래머스/Lv.2] 메뉴 리뉴얼 (Java)

메뉴 리뉴얼

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

---

풀이

가능한 모든 조합

목표 길이 도달 -> 조합 완성

// 조합, 빈도
static Map<String, Integer> HM;

static void comb(char[] arr, int start, int len, StringBuilder sb) {
    if (sb.length() == len) {
        String com = sb.toString();
        HM.put(com, HM.getOrDefault(com, 0) + 1);
        return;
    }

    for (int i = start; i < arr.length; i++) {
        sb.append(arr[i]);
        comb(arr, i + 1, len, sb);
        sb.deleteCharAt(sb.length() - 1);
    }
}

 

2회 이상인 최대 빈도 찾기 -> 최대 빈도 조합 결과에 추가

for (int cnt : HM.values()) {
    if (cnt >= 2) {
        maxCnt = Math.max(maxCnt, cnt);
    }
}

for (String key : HM.keySet()) {
    if (HM.get(key) == maxCnt && maxCnt >= 2) {
        result.add(key);
    }
}

---

코드

import java.util.*;

class Solution {
    // 조합, 빈도
    static Map<String, Integer> HM;
    
    static void comb(char[] arr, int start, int len, StringBuilder sb) {
        if (sb.length() == len) {
            String com = sb.toString();
            HM.put(com, HM.getOrDefault(com, 0) + 1);
            return;
        }
        
        for (int i = start; i < arr.length; i++) {
            sb.append(arr[i]);
            comb(arr, i + 1, len, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    
    public String[] solution(String[] orders, int[] course) {
        List<String> result = new ArrayList<>();
        
        for (int c : course) {
            HM = new HashMap<>();
            int maxCnt = 0;
            
            for (String o : orders) {
                char[] arr = o.toCharArray();
                Arrays.sort(arr);
                comb(arr, 0, c, new StringBuilder());
            }
            
            for (int cnt : HM.values()) {
                if (cnt >= 2) {
                    maxCnt = Math.max(maxCnt, cnt);
                }
            }
            
            for (String key : HM.keySet()) {
                if (HM.get(key) == maxCnt && maxCnt >= 2) {
                    result.add(key);
                }
            }
        }
        
        Collections.sort(result);
        
        return result.toArray(new String[0]);
    }
}