메뉴 리뉴얼

2025-04-11

#JAVA#프로그래머스

문제 링크

문제 풀이 시간 : 1시간

문제 풀이 :

이 문제는 처음 보고 dp로 풀어야 하나? 라고 고민했었는데 아무리 생각해도 풀이법이 떠오르지 않았다.

그래서 조합을 생각했는데 조합으로 해도 경우의 수가 엄청나게 많아지지는 않는 것 같아서

조합으로 풀게 되었다.

먼저, 아래 코드는 특정 주문에 대한 메뉴들의 조합을 만드는 함수이다.

Java

public void find(char[] order, int idx, int len, StringBuilder sb) {
    if (sb.length() == len) {
        map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) + 1);
        return;
    }
    
    for (int i = idx; i < order.length; i++) {
        sb.append(order[i]);
        find(order, i + 1, len, sb);
        sb.deleteCharAt(sb.length() - 1);
    }
}

여기서 order는 주문, idx는 현재 주문에서의 메뉴 인덱스, len은 만들어야 하는 조합의 길이, sb는 만들어진 조합이다.

아래 코드에서 만들어야하는 코스의 길이에 대해 해시맵을 생성하고,

각 주문에 대해 조합을 생성한다.

그 후, 해당 코스 길이에서 최대로 많이 주문된 횟수를 구한다.

그 후, 주문의 수가 2가 넘고 최댓값과 같은 조합을 배열에 추가하면 된다.

Java

for (int i = 0; i < course.length; i++) {
    map = new HashMap<>();
    for (int j = 0; j < orders.length; j++) {
        char[] order = orders[j].toCharArray();
        Arrays.sort(order);
        find(order, 0, course[i], new StringBuilder()); //조합 생성
    }
    
    int max = 0;
    for (int val : map.values()) {
        max = Math.max(max, val);
    }
    
    if (max >= 2) { //주문의 수가 2를 넘어야 함
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() == max) { //최댓값과 같은 조합
                arr.add(entry.getKey());
            }
        }
    }
}

최종 코드

Java

import java.util.*;

class Solution {
    public Map<String,Integer> map;
    
    public void find(char[] order, int idx, int len, StringBuilder sb){
        if(sb.length() == len){
            map.put(sb.toString(), map.getOrDefault(sb.toString(),0)+1);
            return;
        }
        
        for(int i=idx;i<order.length;i++){
            sb.append(order[i]);
            find(order, i+1, len, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    
    public String[] solution(String[] orders, int[] course) {
        String[] answer = {};
        
        ArrayList<String> arr = new ArrayList<>();
        
        for(int i=0;i<course.length;i++){
            map = new HashMap<>();
            for(int j=0;j<orders.length;j++){
                char[] order = orders[j].toCharArray();
                Arrays.sort(order);
                find(order, 0, course[i], new StringBuilder());
            }
            
            int max = 0;
            for(int val : map.values()){
                max = Math.max(max, val);
            }
            
            if (max >= 2) {
                for (Map.Entry<String, Integer> entry : map.entrySet()) {
                    if (entry.getValue() == max) {
                        arr.add(entry.getKey());
                    }
                }
            }
        }
        
        answer = arr.toArray(new String[0]);
        Arrays.sort(answer);
        return answer;
    }
}