메뉴 리뉴얼 (Java, DFS, 프로그래머스)

중복을 허용하지 않는 조합을 만들줄 아는지에 대해 묻는 질문이었다.

 

원하는 개수에 도달했는지 확인하는 int depth 변수 하나와 dfs 내에서 for loop의 현재 인덱스를 저장하는 int index 변수 2가지를 선언하여 각각 관리하는 것이 조합을 만드는 방법이었으나

본인의 경우 index와 depth를 하나의 변수로 처리하려고 하여 주어진 케이스만 맞고 내부 테스트 케이스가 대부분 틀리는 결과가 나왔다. 

 

String을 Alphabetic으로 관리하고자 하면 TreeSet을 이용하기.

String 내의 char를 Alphabetic으로 정렬하려면 char[] -> sort -> 변수 초기화.

 

import java.util.*;

class Solution {
    //course를 돌면서 number마다 조합 생성해서 map에 조합, 빈도로 저장하고 가장 빈도수가 높은 값을 전부 set에 담기.
    void dfs(StringBuilder comb, int depth, int limit, Map<String, Integer> map, int index, String order) {
        if (depth == limit) {
            map.put(comb.toString(), map.getOrDefault(comb.toString(), 0) + 1);
            return;
        }
        //정렬되어있는 값을 조합하는 것이므로 이전 값에 되돌아가지 않게 시작값 index.
        //index와 depth는 다른 값임을 명심. depth는 원하는 값에 대한 측정치이며 index는 현재 위치에 대한 측정치이다.
        for (var i = index; i < order.length(); i++) {
            comb.append(order.charAt(i));
            dfs(comb, depth + 1, limit, map, i + 1, order);
            comb.delete(depth, depth + 1);
        }
    }
    
    public String[] solution(String[] orders, int[] course) {
        var answerSet = new TreeSet<String>();
        //각 주문을 오름차순으로 정렬.
        for (var i = 0; i < orders.length; i++) {
            var temp = orders[i].toCharArray();
            Arrays.sort(temp);
            orders[i] = String.valueOf(temp);
        } 
        for (var number : course) {
            //조합을 만들어서 map에 빈도와 함께 저장.
            var map = new HashMap<String, Integer>();
            for (var order : orders) {   
                var sb = new StringBuilder();
                dfs(sb, 0, number, map, 0, order);
            }
            //각 number에서 가장 빈도가 높은 값 구하기.
            var max = 0;
            for (var i : map.values()) {
                max = Math.max(max, i);
            }
            //최다 빈도에 해당하는 모든 값을 set에 넣기.
            if (max < 2) continue;
            for (var entry : map.entrySet()) {
                if (entry.getValue() == max) {
                    answerSet.add(entry.getKey());
                }
            }
        }
        String[] answer = new String[answerSet.size()];
        var index = 0;
        for (var s : answerSet) {
            answer[index++] = s;
        }
        return answer;
    }
}