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

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

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

 

문제 해석

기존 단품으로만 제공하는 메뉴를 조합해서 코스요리 형태로 재구성하려고 합니다.

손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리로 구성하려고 합니다.

최소 2가지 이상의 단품메뉴로 구성하려고 합니다.

또한 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함합니다.

 

예를 들어 6명이 손님한 단품메뉴들의 조합이 다음과 같다고 예시를 들어보겠습니다.

1번 손님	A, B, C, F, G
2번 손님	A, C
3번 손님	C, D, E
4번 손님	A, C, D, E
5번 손님	B, C, F, G
6번 손님	A, C, D, E, H

가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

요리 2개 코스	A, C	1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스	C, D, E	3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스	B, C, F, G	1번, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스	A, C, D, E	4번, 6번 손님으로부터 총 2번 주문됐습니다.

문제 풀이 전 설계

A-Z의 알파벳 대문자로 메뉴가 표기되기 때문에 배열을 만들거나 HashMap을 통해 알파벳을 관리하고자 합니다.

 

그리고 정렬을 하여 자주나오는 문자열을 조합하려고 했습니다.

 

즉, "XYZ", "AY", "XYA" 에서 요리 3개 코스를 만들기위해서 YXA를 뽑으면 된다고 생각했습니다.

만약 요리 2개 코스를 만들기 위해서는 YX YA를 뽑으면 된다고 생각했습니다.
X=2, Y=3, Z=1, A=2

 

하지만 이는 문제를 잘못 해석한 것입니다.

 

하나의 손님이 주문한 단품메뉴에서 3개를 뽑아야하므로 XYZ, XYA가 후보로 올 수 있고 

XYZ, XYA는 1번만 나왔기 때문에 문제의 조건에 의해 제외됩니다.

 

문제 풀이

손님이 주문한 요리의 단품메뉴를 조합하는게 키 포인트였습니다.

ABCFG의 경우에는 요리 2개코스를 만들수 있는 부분이 5C2입니다.

 

즉, AB AC AF AG BC BF BG CF CG가 나옵니다.

 

이런식으로 1번~n번손님 nC2를 하여 요리 2개 코스가 가장 빈번하게 나온 값을 기록하는 식으로 풀이를 해야 합니다.

 

그 다음에는 1번~n번손님 nC3.. 이런식으로 course에 대해서 반복하여 줍니다.

 

코드

import java.util.*;

class Solution {

    List<String> answerList = new ArrayList<>();
    Map<String, Integer> hashMap = new HashMap<>();

    public String[] solution(String[] orders, int[] course) {

        // 1. 각 Order 정렬
        for (int i = 0; i < orders.length; i++) {
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = String.valueOf(arr);
        }

        // 2. 각 order를 기준으로 courseLength 만큼의 조합 만들기
        for (int courseLength : course) {
            for (String order : orders)
                combination("", order, courseLength);

            // 3. 가장 많은 조합 answer에 저장
            if (!hashMap.isEmpty()) {
                List<Integer> countList = new ArrayList<>(hashMap.values());
                int max = Collections.max(countList);

                if (max > 1)
                    for (String key : hashMap.keySet())
                        if (hashMap.get(key) == max)
                            answerList.add(key);
                hashMap.clear();
            }
        }

        Collections.sort(answerList);
        String[] answer = new String[answerList.size()];
        for (int i = 0; i < answer.length; i++)
            answer[i] = answerList.get(i);

        return answer;
    }

    public void combination(String order, String others, int count) {
        // 탈출 조건 : count == 0
        if (count == 0) {
            hashMap.put(order, hashMap.getOrDefault(order, 0) + 1);
            return;
        }

        // 0부터 length까지 조합
        for (int i = 0; i < others.length(); i++)
            combination(order + others.charAt(i), others.substring(i + 1), count - 1);
    }
    public static void main(String[] args){
        Solution sol = new Solution();
        String[] orders = {"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"};
        int[] course = {2,3,4};
        System.out.println(sol.solution(orders, course));
    }
}