(2021카카오) 메뉴 리뉴얼 Java

이 문제의 가장 큰 포인트는 조합이다.

 

1. 조합

각 문자열에 대하여 나올수 있는 조합을 구하는데, 그 조합을 nCr이라고 할때,

r값은 course[i]로 주어진 것이고,

n값은 각 코스요리의 길이 이므로 orders[i].length로 주어진다.

 

2. 알파벳순 정렬

고려하는 새로운 코스요리 세트에 대하여, AB와 BA는 같은 것이므로 오름차순 정렬을 시행한다.

이는 map에 집어넣을때부터 비교연산을 하는 모든 경우에서 필요하므로 미리 정렬 시켜야한다.

 

 

실패코드

테스트케이스 3만 성공한다.

import java.util.*;

class Solution {
    private static Map<String, Integer> map = new HashMap<>();

    static void print(String arr, boolean[] visited, int n) {
        String s = "";
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                s += arr.charAt(i);
            }
        }
        char[] charArr = s.toCharArray(); // String to Char Array
        Arrays.sort(charArr); // Char Array 알파벳 순 정렬
        String result = new String(charArr);

        map.put(result, map.getOrDefault(result, 0) + 1);
    }

    static void combination(String arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            print(arr, visited, n);
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }

    public String[] solution(String[] orders, int[] course) {
        for (int i : course) {//i개를 뽑는 시행
            for (String order : orders) {
                int n = order.length();
                boolean[] visited = new boolean[n];
                combination(order, visited, 0, n, i);
            }
        }
        PriorityQueue<String> pq = new PriorityQueue<>();
        for (int i = 0; i < course.length; i++) {
            Stack<String> stack = new Stack<>();
            int longestLength = 0;
            for (String s : map.keySet()) {
                if (map.get(s) >= 2 && s.length() == course[i]) {
                    if (map.get(s) > longestLength) {
                        while (!stack.isEmpty()) {
                            stack.pop();
                        }
                        stack.push(s);
                    } else if (map.get(s) == longestLength) {//같은경우 넣어놓기
                        stack.push(s);
                    }
                }
            }
            pq.addAll(stack);
        }
        String[] answer = new String[pq.size()];
        int size = pq.size();
        for(int i=0; i<size; i++){
            answer[i] = pq.poll();
        }

        return answer;
    }
}

 

테스트케이스

조건이 다음과 같이 충족해야한다.

 

course[i]=2일때, 3일때, ...일때 각각에 대하여

 

2회 이상 사용된 코스 ex) WX WX

  => 그중에서 가장 많이 사용된 코스(가장 많이 사용된 코스가 여러개인 경우 모두)

 

---

테스트케이스3번

위의 테스트케이스에서는 i=2일때 2회이상 사용된 모든 경우의 코스는

<WX, 2회>, <XY, 2회> 이다.

max = 2회이므로, max=2 인 문자열코스를 채택한다.

 

따라서 i=2일때, [WX,  XY] (오름차순정렬) 두가지이다.

 

---

 

 

성공코드

import java.util.*;

class Solution {
    static HashMap<String, Integer> map;// <key , value> = <String, counting개수>
    static int m;

    public String[] solution(String[] orders, int[] course) {
        PriorityQueue<String> pq = new PriorityQueue<>();

        for (int i = 0; i < course.length; i++) {//각각의 "요리의 개수"에 대하여 실행.
            map = new HashMap<>();//각 i일때마다 초기화!!!
            m = 0;
            for (int j = 0; j < orders.length; j++) {
                find(0, "", course[i], 0, orders[j]);
            }
            for (String s : map.keySet()) {//각 i일때마다 초기화되므로
                if (map.get(s) == m && m > 1) {//최대값m인 value를 가진 key값을 찾아서
                    pq.offer(s);//우선순위 큐에다가 집어넣는다.
                }
            }
        }
        String ans[] = new String[pq.size()];
        int k = 0;
        while (!pq.isEmpty()) {
            ans[k++] = pq.poll();
        }
        return ans;
    }

    static void find(int cnt, String str, int targetNum, int idx, String word) {
        if (cnt == targetNum) {
            char[] c = str.toCharArray();//문자열 하나하나에 대하여 알파벳순으로
            Arrays.sort(c);//정렬시킴.
            String temps = "";
            for (int i = 0; i < c.length; i++) //정렬한거 다시합치기
                temps += c[i];
            map.put(temps, map.getOrDefault(temps, 0) + 1);//각 음식세트 카운팅값.
            m = Math.max(m, map.get(temps));//map에다가 이렇게 넣으면서! 카운팅최대값을 미리 구해놓는다.
            return;
        }
        for (int i = idx; i < word.length(); i++) {
            char now = word.charAt(i);
            find(cnt + 1, str + now, targetNum, i + 1, word);
        }
    }
}