문제 풀이

문제에 나와있는대로 구현을 했지만 시간초과가 날 줄 알고 일단 제출해보고 커팅을 해보자 하고 제출했는데 시간초과가 나지 않았다.

문자열들을 백트래킹을 통해서 길이가 orders[i]인 문자열의 조합을 구하고 HashMap의 key값으로 사용하고 value는 몇번 나오는지 빈도수를 저장했다.

각 문자열 길이의 조합마다 Set을 구성해주고, 어떤 문자열이 몇번 나오는지 배열에 담아 등장 빈도수 기준으로 내림차순으로 정렬했다.

가장 첫번째 원소의 빈도수가 max고 그다음 원소부터 확인하면서 max하고 같으면 answer에 추가해준다. 그렇지 않다면 break.

마지막으로 answer을 사전순으로 정렬하면 된다.

문제 링크

Programmers/72411

소스코드

PS/Programmers/72411.java

 import java.io.*;

    import java.util.*;

class Solution {
      static boolean []select = new boolean[27];
        static HashMap<String, Integer> cnt = new HashMap<>();
        static List<String> []list = new ArrayList[11];
        static class Entity implements Comparable<Entity>
        {
            String s;
            int cnt ;

            public Entity(String s, int cnt) {
                this.s = s;
                this.cnt = cnt;
            }

            @Override
            public int compareTo(Entity o) {
                return o.cnt-this.cnt;
            }
        }
    static void solve(int cur,int max,int idx, String str)
        {
            if(cur == max)
            {
                int c =0 ;
                String s ="";
                for(int i=0;i<=26;i++)
                {
                    if(select[i]) {
                        s += (char) ('A' + i);
                        c++;
                    }
                }
                if(c == max) {
                    if (cnt.containsKey(s))
                        cnt.put(s, cnt.get(s) + 1);
                    else {
                        cnt.put(s, 1);
                        list[max].add(s);
                    }
                }
                return;

            }

            for(int i=idx;i<str.length();i++)
            {
                if(!select[str.charAt(i) -'A']) {
                    select[str.charAt(i)-'A'] = true;
                    solve(cur + 1, max, i+1, str);
                    select[str.charAt(i)-'A'] =false;
                }
            }
        }
    public String[] solution(String[] orders, int[] course) {
          ArrayList<String> ans = new ArrayList<>();
            for(int i=0;i<course.length;i++)
                list[course[i]] = new ArrayList<>();
            for(int i=0;i<course.length;i++)
            {
                for(int j=0;j<orders.length;j++) {
                    solve(0, course[i], 0, orders[j]);
                }
                ArrayList<Entity> cnts = new ArrayList<>();
                for(int j=0;j<list[course[i]].size();j++) {
                    if(cnt.get(list[course[i]].get(j))>=2) {
                        cnts.add(new Entity(list[course[i]].get(j), cnt.get(list[course[i]].get(j))));
                    }
                }
                Collections.sort(cnts);
                if(!cnts.isEmpty())
                {
                    int max = cnts.get(0).cnt;
                    ans.add(cnts.get(0).s);
                    for(int j=1;j<cnts.size();j++)
                    {
                        if(cnts.get(j).cnt != max)
                            break;
                        ans.add(cnts.get(j).s);
                    }
                }

            }
            Collections.sort(ans);
   String []answer = ans.toArray(new String[0]);

        return answer;
    }
}