[프로그래머스/Java] 72411번 메뉴 리뉴얼

프로그래머스 메뉴 리뉴얼 [2021 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/72411

.

주어진 개수(course[i])만큼의 조합 중, 가장 많이 주문 된 조합을 또 골라내야 한다.
완전탐색을 통해 가장 많이 발생한 조합을 찾아내야한다는 말이다.

.

조합에 대한 완전탐색을 받아들였다면, 다음 고민으로 들어서야 한다.

[방안 1]
1. 모든 course[i]에 대해 각 order에서 course[i]개를 뽑아내는 조합을 각각 구한다.
2. 두 개 이상의 order에서 발생한 조합 중, 가장 많이 발생한 조합을 result에 넣는다.

[방안 2]
1. 각 order에서 가능한 모든 조합을 구한다.
2. 모든 course[i]에 대해, course[i]개짜리 조합 중 중복 이상으로 가장 많이 발생한 조합을 result에 넣는다.

결국 course가 먼저냐 order가 먼저냐의 문제인데, 나는 [방안 2]를 채택했다.

• orders의 길이가 20 이하, order의 길이가 10 이하이므로 [방안 1]은 최대 20*(2^10 - 1 - 10) = 20260가지, [방안 2]는 최대 20 * 2^10 = 20480가지 조합을 구해야 하므로 유의미한 차이가 없다.
• [방안 2]가 오히려 조합을 구하는 과정에서 발생하는 중복연산을 막는다. 3개짜리 조합은 결국 2개짜리 조합에서 한 개 더 뽑은 것이다.

.

다음으로, 조합을 구하는 방법에 대해 고민해야 한다.
조합을 구할 때 비트연산을 하거나 dfs를 사용하는 것이 일반적인데, 나는 dfs를 채택했다.

import java.util.*;
class Solution {
    public String[] solution(String[] orders, int[] course) {
        Map<String, Integer> orderMap = new HashMap<>();
        for(String order : orders){
            char[] charArr = order.toCharArray();
            Arrays.sort(charArr);
            Map<String, Integer> tmpOrderMap = dfs(new String(charArr));
            tmpOrderMap.forEach((key, value) -> orderMap.merge(key, value, (v1, v2) -> v1 + v2));
        }
        Set<String> resultSet = new TreeSet<>();
        for(int count : course){
            int maxCount = 2;
            Set<String> courseSet = new TreeSet<>();
            for(String key : orderMap.keySet()){
                if(key.length() == count){
                    if(orderMap.get(key) > maxCount){
                        courseSet.clear();
                        courseSet.add(key);
                        maxCount = orderMap.get(key);
                    } else if (orderMap.get(key) == maxCount){
                        courseSet.add(key);
                    }
                }
            }
            resultSet.addAll(courseSet);
        }
        String[] answer = resultSet.toArray(new String[resultSet.size()]);
        return answer;
    }
    public Map<String, Integer> dfs(String order){
        Map<String, Integer> orderMap;
        if(order.length() <= 1) {
            orderMap = new HashMap<>();
            orderMap.put("", 1);
            orderMap.put(order, 1);
        } else {
            orderMap = dfs(order.substring(1));
            Map<String, Integer> tmpOrderMap = new HashMap<>();
            for(String key : orderMap.keySet())
                tmpOrderMap.put(order.substring(0, 1) + key, 1);
            orderMap.putAll(tmpOrderMap);
        }
        return orderMap;
    }
}

.
.

Map 클래스에 유용한 메소드가 많이 구현되어있다는 걸 알게 해 준 문제였다.

최근에 merge 메소드를 접하고 야심차게 사용했는데, getOrDefault라는 메소드도 있더라..
orderMap을 전역변수로 두거나 인수-인자로 넘겨가며 재활용하는 방식으로 구현했더라면 편리하게 쓰였을 것이다.

Collection에 대해서만큼은 공식 문서를 제대로 읽어보아야겠다. 아직 모르는 게 참 많네. 🥲