문제

문제링크

접근

• 전체 부분집합을 구하는데 dfs를 사용하였다. 이 방법에 빨리 익숙해져야 할 것 같다.
• set을 이용하면서 시간복잡도를 줄이려고 했는데 막상 구현 후에는 그 장점을 많이 이용하지 못한 것 같아서 아쉽다.
• 이후 숏코딩을 도전해볼 필요가 있다.

풀이

import java.util.*;

class Solution {
    HashMap<String, Integer> combis = new HashMap<>();

    public List<String> solution(String[] orders, int[] course) {
        List<String> answer = new ArrayList<>();
        Best[] bests = new Best[course.length];

        for (int i = 0; i < course.length; i++) {
            bests[i] = new Best();
        }

        for (String str : orders) {
            boolean[] visited = new boolean[str.length()];
            char[] a = str.toCharArray();
            Arrays.sort(a);
            dfs(a, visited, 0);
        }

        Set<String> set = combis.keySet();
        for (String str : set) {
            for (int i = 0; i < course.length; i++) {
                if (course[i] == str.length()) {
                    if (combis.get(str) < 2)
                        break;
                    if (combis.get(str) > bests[i].count) {
                        bests[i].combis.clear();
                        bests[i].combis.add(str);
                        bests[i].count = combis.get(str);
                    } else if (combis.get(str) == bests[i].count) {
                        bests[i].combis.add(str);
                    }
                    break;
                }
            }
        }

        for (int i = 0; i < course.length; i++) {
            for (String string : bests[i].combis) {
                answer.add(string);
            }
        }

        Collections.sort(answer);

        return answer;
    }

    public void dfs(char[] currOrders, boolean[] visited, int idx) {
        if (idx == currOrders.length) {
            String combi = "";
            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {
                    combi += currOrders[i];
                }
            }

            if (combi.length() < 2)
                return;

            if (combis.containsKey(combi)) {
                combis.replace(combi, combis.get(combi) + 1);

            } else {
                combis.put(combi, 1);
            }

            //System.out.println(combi + " " + combis.get(combi));
            return;
        }

        visited[idx] = true;
        dfs(currOrders, visited, idx + 1);
        visited[idx] = false;
        dfs(currOrders, visited, idx + 1);
    }
    
    class Best {
        ArrayList<String> combis = new ArrayList<>();
        int count = 0;
    }
}