[프로그래머스] 메뉴 리뉴얼 / 2021 KAKAO BLIND RECRUITMENT - JAVA

🔗 문제 링크

[프로그래머스] 메뉴 리뉴얼 / 2021 KAKAO BLIND RECRUITMENT

코딩테스트 연습 - 메뉴 리뉴얼

 

📝 풀이 과정

메뉴의 코스의 수가 주어지고, 코스의 수별로 가장 많이 시킨 메뉴 조합을 구하는 문제이다.

1. 주문별로 가능한 2이상의 모든 조합을 구한다
2. 조합된 메뉴의 수를 Map에 넣어가며 개수를 누적한다

위의 아이디어로 구현하였다.

 

먼저 메뉴의 수대로 모아보기 위해 Map<Integer, Map<String, Integer>> courseMap을 생성하였다. 처음 Integer Key는 '메뉴의 수'이고, 이후로는 메뉴의 등장 횟수를 누적하기 위해 <메뉴조합, 등장 횟수>를 저장하였다.

 

 

void perm(char[] order, String course, int idx) {
  if (courseMap.containsKey(course.length())) {
    int len = course.length();
    courseMap.get(len).put(course, courseMap.get(len).getOrDefault(course, 0) + 1);
  }
  for (int i = idx; i < order.length; i++)
    perm(order, course + order[i], i + 1);
}

이후, 가능한 메뉴의 조합을 구하기위해 perm함수를 구현해 순차적으로 추가할 메뉴들을 order에 누적해 가며 모든 조합을 구하고, 메뉴의 수에 해당하는 key값에 해당하는 메뉴의 횟수를 하나 증가시켜주었다.

 

모든 조합이 끝나고 나서 Map의 Key별로 묶어보면서 메뉴 조합에서 가장 많이 등장한 조합을 찾기위해 value순으로 정렬하고, max값과 동일한 메뉴 조합을 모두 답 List에 넣고 반환할 때 배열로 변환해 반환했다.

 

 

💻 코드

import java.util.*;

public class Solution {
    Map<Integer, Map<String, Integer>> courseMap = new HashMap<>();

    public String[] solution(String[] orders, int[] course) {
        for (int c : course) courseMap.put(c, new HashMap<>());

        for (String o : orders) {
            char[] order = o.toCharArray();

            Arrays.sort(order);
            perm(order, "", 0);
        }

        List<String> list = new ArrayList<>();
        for (Map.Entry<Integer, Map<String, Integer>> map : courseMap.entrySet()) {
            List<Map.Entry<String, Integer>> courseList = new ArrayList<>(map.getValue().entrySet());
            if (courseList.size() == 0) continue;

            courseList.sort(Comparator.comparingInt(o -> o.getValue()));

            int idx = courseList.size() - 1;
            int max = Math.max(courseList.get(idx).getValue(), 2);

            while (idx >= 0 && courseList.get(idx).getValue() == max)
                list.add(courseList.get(idx--).getKey());
        }

        list.sort(null);
        return list.toArray(new String[0]);
    }

    void perm(char[] order, String course, int idx) {
        if (courseMap.containsKey(course.length())) {
            int len = course.length();
            courseMap.get(len).put(course, courseMap.get(len).getOrDefault(course, 0) + 1);
        }
        for (int i = idx; i < order.length; i++)
            perm(order, course + order[i], i + 1);

    }
}