프로그래머스 - 메뉴 리뉴얼 (JAVA)

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

문제 풀이

처음에 문자열 비교로 접근해 엄청 해멨다. 이 문제는 문자열 비교로 접근을 하는게 아니라 한 사람이 시킨 메뉴 코스를 이용해 만들 수 있는 경우의 수를 만들어 비교하는 문제다.

1. 코스를 사전 순서로 저장할 수 있도록 주문을 정렬해준다.
2. 한 손님이 주문한 단품 메뉴들로 만들 수 있는 모든 코스 조합을 만들어준다.
3. 코스내 메뉴 개수에 따라 가장 많이 선택된 횟수를 저장해 놓는다.
4. 코스를 선택할때 코스내 메뉴가 메뉴 개수에서 가장 많이 선택된 횟수와 같다면 넣어준다.

모든 코스를 만들어주는 함수

public void findAllCourse(String order, String subOrder, int depth) {
    if (depth == order.length()) {
        if (subOrder.length() > 1) {
            if (map.containsKey(subOrder)) {
                int value = map.get(subOrder);
                map.put(subOrder, value + 1);
            } else {
                map.put(subOrder, 1);
            }
        }
        return;
    }

    findAllCourse(order, subOrder + order.charAt(depth), depth + 1);
    findAllCourse(order, subOrder, depth + 1);
}

전체 소스

import java.io.*;
import java.util.*;

class Solution {
    Map<String, Integer> map = new TreeMap<>();

    public void findAllCourse(String order, String subOrder, int depth) {
        if (depth == order.length()) {
            if (subOrder.length() > 1) {
                if (map.containsKey(subOrder)) {
                    int value = map.get(subOrder);
                    map.put(subOrder, value + 1);
                } else {
                    map.put(subOrder, 1);
                }
            }
            return;
        }

        findAllCourse(order, subOrder + order.charAt(depth), depth + 1);
        findAllCourse(order, subOrder, depth + 1);
    }

    public String[] solution(String[] orders, int[] course) {
        for (String order : orders) {
            // 문자열내 문자들을 사전 순서대로 정렬
            char[] charArr = order.toCharArray();
            Arrays.sort(charArr);
            String sortedOrder = new String(charArr);

            // 주문한 메뉴들로 만들 수 있는 모든 코스 조합을 만들어준다.
            findAllCourse(sortedOrder, "", 0);
        }

        int[] maxValues = new int[101];

        ArrayList<String> result = new ArrayList<>();

        map.forEach((key, value) -> maxValues[key.length()] = Math.max(maxValues[key.length()], value));
        map.forEach((key, value) -> {
            if (value >= maxValues[key.length()] && value > 1) {
                for (int i = 0; i < course.length; i++) {
                    if (course[i] == key.length()) {
                        result.add(key);
                    }
                }
            }
        });

        String[] answer = new String[result.size()];
        int index = 0;
        for (String s : result) {
            answer[index++] = s;
        }

        return answer;
    }
}