프로그래머스 - 메뉴 리뉴얼 - 정렬 - Java

1. 문제

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

2. 풀이

참고 풀이

✨기초

1. char[] -> String

orders[i] = String.valueOf(orderCh);

2. map.getOrDefault -> 가능한 개수 넣어주기.

map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) + 1);

핵심 ✨Point

1. orders[i] 문자열들 오름차순 정렬

for(int i = 0; i < orders.length; i++) {
	char orderCh[] = orders[i].toCharArray();
	Arrays.sort(orderCh);
	orders[i] = String.valueOf(orderCh);
}

2. course 조합이 5인데 orders[i] 길이가 2이면 조합을 만들 수 없기 때문에 가능한 것만 수행한다.

if(course[i] <= orders[j].length()) {
	dfs(orders[j], new StringBuilder(), 0, 0, course[i]);
}

3. 조합을 구해주는 dfs

public static void dfs(String str, StringBuilder sb, int start, int depth, int n) {
	if(depth == n) {
		map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) + 1);
		return;
	}
	for(int i = start; i < str.length(); i++) {
		sb.append(str.charAt(i));
		dfs(str, sb, i+1, depth+1, n);
		sb.deleteCharAt(depth);
	}
}

4. 2개 이상의 조합부터 따져준다.

for(String str : map.keySet()) {
	if(max >= 2 && map.get(str) == max) {
		answer.add(str);
	}
}

3. 전체 코드

import java.util.*;

class Solution {
    Map<String, Integer> map;
    ArrayList<String> list = new ArrayList<>();
    int max;
    
    public String[] solution(String[] orders, int[] course) {
        for(int i = 0; i < orders.length; i++){
            char[] orderCh = orders[i].toCharArray();
            Arrays.sort(orderCh);
            orders[i] = String.valueOf(orderCh);
        }
        
        for(int i = 0; i < course.length; i++){
            map = new HashMap<>();
            max = Integer.MIN_VALUE;
            for(int j = 0; j < orders.length; j++){
                if(course[i] <= orders[j].length()){
                    comb(orders[j], new StringBuilder(), 0, 0, course[i]);
                }   
            }
            
            for(String str : map.keySet()) {
                max = Math.max(max, map.get(str));
            }
            
            for(String str : map.keySet()){
                if(max >= 2 && map.get(str) == max){
                    list.add(str);
                }
            }
        }
        Collections.sort(list);
        
        return list.toArray(new String[list.size()]);
    }
    
    public void comb(String str, StringBuilder sb, int start, int depth, int n){
        if(depth == n){
            int count = map.getOrDefault(sb.toString(), 0) + 1;
            //max = Math.max(max, count);
            map.put(sb.toString(), count);
            return;
        }
        
        for(int i = start; i < str.length(); i++){
            sb.append(str.charAt(i));
            comb(str, sb, i+1, depth+1, n);
            sb.deleteCharAt(depth);
        }
    }
}