[2021 카카오 블라인드] 메뉴 리뉴얼 (JAVA)

문제

---

풀이

푸는 방법은 바로 떠올랐지만 세부사항을 놓치는 바람에 코드 짜는 데는 생각보다 오래 걸린 문제였다. 그치만 풀어내서 뿌듯했다.

1. 주어진 length의 가능한 모든 조합을 만들어서, 그 조합(코스)가 후보에 추가될 수 있는지 체크한다.
2. makeCombinations()는 DFS로 주어진 order 문자열에서 length만큼 조합을 만들고 combinations 리스트에 저장한다.
3. findCandidateCourses()는 combinations에 있는 각각의 course가 총 몇 번 주문이 들어왔는지 체크하고 2번 이상 주문된 것들만 candidates에 저장한다.
   • 순서만 다른 같은 코스가 중복 저장되는 것을 방지하기 위해 sortString() 처리를 한다.
   • 길이가 같은 코스들 중에서는 가장 많이 주문된 것만 answer에 저장해야 하기 때문에 maxCountOnCurrentLength에 최대주문회수를 저장한다.
4. 체크 중인 length에 대한 탐색이 끝나면 getAnswerFromCandidates()에서 candidates에서 주문회수가 최대인 candidates만 answer에 저장한다.
5. 최종적으로 answer을 오름차순으로 정렬하여 리턴한다.

---

코드

import java.util.*;

class Solution {

    private String[] orders;
    private int[] courseLengths;
    
    private List<String> answer = new ArrayList<>();
    private Set<String> checkedCourses = new HashSet<>();
    private List<String> combinations;
    private List<Course> candidates;
    private int maxCountOnCurrentLength;

    public String[] solution(String[] orders, int[] course) {
        this.orders = orders;
        this.courseLengths = course;
        findAvailableCourses();
        this.answer.sort(String::compareTo);
        return this.answer.toArray(new String[0]);
    }

    private void findAvailableCourses() {
        for (int length : this.courseLengths) {
            this.candidates = new ArrayList<>();
            this.maxCountOnCurrentLength = 0;
            for (String order : this.orders) {
                makeCombinations(order, length);
                if (!this.combinations.isEmpty())
                    findCandidateCourses();
            }
            getAnswerFromCandidates();
        }
    }

    private void makeCombinations(String order, int length) {
        char[] menus = order.toCharArray();
        boolean[] visited = new boolean[menus.length];
        char[] result = new char[menus.length];
        this.combinations = new ArrayList<>();
        doCombination(menus, visited, result, length, 0, 0);
    }

    private void doCombination(char[] menus, boolean[] visited, char[] result, int length, int start, int depth) {
        if (depth == length) {
            this.combinations.add(new String(result).trim());
            return;
        }

        for (int i = start; i < menus.length; i++) {
            visited[i] = true;
            result[depth] = menus[i];
            doCombination(menus, visited, result, length, i + 1, depth + 1);
            visited[i] = false;
            result[depth] = 0;
        }
    }

    private void findCandidateCourses() {
        for (String course : this.combinations) {
            course = sortString(course);
            if (!this.checkedCourses.contains(course)) {
                this.checkedCourses.add(course);
                int orderedCount = getOrderedCount(course);
                if (orderedCount > 1) {
                    this.candidates.add(new Course(course, orderedCount));
                    this.maxCountOnCurrentLength = Math.max(this.maxCountOnCurrentLength, orderedCount);
                }
            }
        }
    }

    private String sortString(String course) {
        char[] courseArr = course.toCharArray();
        Arrays.sort(courseArr);
        return new String(courseArr);
    }

    private int getOrderedCount(String course) {
        int count = 0;
        for (String order : this.orders)
            if (orderContainCourse(order, course)) count++;
        return count;
    }

    private boolean orderContainCourse(String order, String course) {
        for (char menu : course.toCharArray())
            if (!order.contains(menu + "")) return false;
        return true;
    }

    private void getAnswerFromCandidates() {
        for (Course candidate : this.candidates)
            if (candidate.orderedCount == this.maxCountOnCurrentLength)
                this.answer.add(candidate.menus);
    }
}

class Course {
    String menus;
    int orderedCount;

    public Course(String menus, int orderedCount) {
        this.menus = menus;
        this.orderedCount = orderedCount;
    }
}