[v2] 메뉴 리뉴얼

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

 

1. orders를 오름차순으로 정렬한다.

 

2-1. 모든 orders[i] 에 대해, course[j] 개의 원소를 뽑은 수열 (조합)을 도출한다.

2-2. 뽑은 수열들을 map<key, value>에 merge한다.

2-3. 동시에, 가장 높은 value를 mapMax로 놓는다.

 

3. map을 순회하며, value가 mapMax인 key를 list에 넣는다.

 

4. list를 정렬하고 배열로 바꿔 리턴한다.

 

import java.util.*;

class Solution {

    int O, C, mapMax;
    Map<String, Integer> map = new HashMap<>();
    List<String> total = new ArrayList<>();

    void solve(int S, String s, int depMax, int dep, int st, String now) {

       if(dep == depMax) {

          map.merge(now, 1, (ov, nv) -> {
             mapMax = Math.max(ov + 1, mapMax);
             return ov + 1;});

          return;
       }

       for(int i=st; i<S; i++) {
          solve(S, s, depMax, dep + 1, i + 1, now + s.charAt(i));
       }

    }

    public String[] solution(String[] orders, int[] course) {
       O = orders.length;
       C = course.length;


       for(int i=0; i<O; i++) {
          StringBuilder sb = new StringBuilder();

          char[] tmp = orders[i].toCharArray();
          Arrays.sort(tmp);

          for(int j=0; j<tmp.length; j++) {
             sb.append(tmp[j]);
          }

          orders[i] = sb.toString();
       }



       for(int i=0; i<C; i++) {
          map.clear();
          mapMax = 0;
          List<String> courseList = new ArrayList<>();
          int c = course[i];

          for(int j=0; j<O; j++) {
             String s = orders[j];
             int S = s.length();

             // 요구하는 코스의 길이보다 주문 메뉴가 작은 경우
             // course 배열에는 같은 값이 중복해서 들어있지 않습니다.
             if(c > S) continue;

             solve(S, s, c, 0, 0, "");
          }

          for (Map.Entry<String, Integer> entry : map.entrySet()) {
             if(entry.getValue() == mapMax) {
                total.add(entry.getKey());
             }
          }
       }

       Collections.sort(total);

       int T = total.size();
       String[] answer = new String[T];

       for(int i=0; i<T; i++)
          answer[i] = total.get(i);

       return answer;
    }
}