2021 KAKAO BLIND RECRUITMENT 2번[메뉴 리뉴얼] 해설

링크

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

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

 

1. 분류

백트래킹

 

2. 풀이

음식점은 손님이 최소 2번 이상 주문한 단품 메뉴 중 가장 많이 주문한 단품 메뉴를 골라서 코스 요리를 새로 만들고자 한다.

입력으로 1번 ~ n번 손님이 주문한 메뉴 목록, 코스 요리로 구성할 단품 메뉴의 개수가 주어지고,

출력은 새로 구성한 코스요리 목록을 내보내야 한다.

 

제한사항을 먼저 살펴보자.

최대 크기가 전부 10의 자리로, 꽤 작은 편이다.

그렇다면 완전탐색으로 해결할 수 있다.

 

작성한 로직은 아래 순서를 따른다.

1. 손님이 주문한 단품 요리 목록(orders)에서 단품 메뉴의 조합을 구한다.
   • 손님이 주문한 메뉴의 개수가 n개이며 순서는 무조건 알파벳순이다.
   • 조합의 수는 nC0 + nC1 + nC2 + ... nCn = n^2 (단 문제 조건에 의해 2개 이상 조합만 구해야 하므로 nC0, nC1은 빼준다)
   • 따라서 조합을 구하는 시간복잡도는 O(n^2)이 된다. 
   • 손님이 m명이고 각 손님이 n개를 주문했다고 가정하면 O(n^2 * m)가 된다.
   • 입력에서 주어진 [코스 요리의 단품 메뉴 개수]에 맞는 코스 요리만 선정한다.
   • 모든 손님의 주문 메뉴를 모아서 조합을 구하려는 생각은 좋지 않다.
     
     • 전혀 매칭되지 않는 코스요리 메뉴가 나올 수 있다.
2. 1에서 구한 단품 메뉴 조합의 중복을 제거한다.
   • 단품 메뉴를 저장할 때 set같은 자료구조를 사용하면 간편하다.
3. 손님의 주문 목록을 순회하며 단품 메뉴 조합의 주문 회수를 구한다.
   • 코드에선 computeMenuCounter가 담당한다.
   • set의 containsAll을 활용하기 위해 메뉴를 Set<Character>로 변환하여 전달했다. 
4. 3에서 구한 결과를 주문 회수로 내림차순 정렬한다.
   • entry는 map에 저장된 key, value 쌍이다.
5. 4에서 구한 결과를 순회하며 입력에서 주어진 [코스 요리의 단품 메뉴 개수]에 맞는 결과를 뽑아낸다.

 

 

3. 소스코드

Solution

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class Solution {

    private int[] courses;
    private final StringBuilder current = new StringBuilder();
    private final Set<String> combinations = new HashSet<>();

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

        this.courses = courses;

        for (String order : orders) {
            var orderArray = order.toCharArray();
            Arrays.sort(orderArray);
            combination(orderArray, 0, order.length());
        }

        var menuCounter = computeMenuCounter(
            Arrays.stream(orders)
                  .map(this::toCharSet)
                  .collect(Collectors.toList()));

        var entries = getSortedEntries(menuCounter);

        return getAnswer(entries);
    }

    private void combination(char[] orderChars, int index, int max) {

        if (index >= max) {
            return;
        }

        for (int i = index; i < max; i++) {

            current.append(orderChars[i]);
            int length = current.length();
            for (int course : courses) {
                if (length == course) {
                    combinations.add(current.toString());
                    break;
                }
            }

            combination(orderChars, i + 1, max);
            current.deleteCharAt(length - 1);
        }
    }

    private Map<String, Integer> computeMenuCounter(List<Set<Character>> ordersSet) {

        var map = new HashMap<String, Integer>();

        for (var orderSet : ordersSet) {
            for (var comb : combinations) {
                if (contains(orderSet, comb)) {
                    map.put(comb, map.getOrDefault(comb, 0) + 1);
                }
            }
        }

        return map;
    }

    private ArrayList<Entry<String, Integer>> getSortedEntries(Map<String, Integer> map) {

        var list = new ArrayList<>(map.entrySet());
        list.sort((o1, o2) -> o2.getValue() - o1.getValue());

        return list;
    }

    private String[] getAnswer(ArrayList<Entry<String, Integer>> entries) {

        var result = new ArrayList<String>();
        var maxCounts = new HashMap<Integer, Integer>();

        for (var entry : entries) {

            int count = entry.getValue();
            if (count <= 1) {
                continue;
            }

            int courseSize = entry.getKey().length();

            if (count >= maxCounts.getOrDefault(courseSize, 0)) {
                maxCounts.put(courseSize, count);
                result.add(entry.getKey());
            }
        }

        Collections.sort(result);

        var answer = new String[result.size()];
        for (int i = 0; i < result.size(); i++) {
            answer[i] = result.get(i);
        }

        return answer;
    }

    private Stream<Character> stringToCharStream(String s) {
        return s.chars().mapToObj(i -> (char) i);
    }

    private boolean contains(Set<Character> set, String s) {
        return stringToCharStream(s).allMatch(set::contains);
    }

    private Set<Character> toCharSet(String s) {
        return stringToCharStream(s).collect(Collectors.toSet());
    }
}

 

TestCode

import static org.junit.jupiter.api.Assertions.assertEquals;

import java.util.Arrays;
import java.util.stream.Stream;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

class SolutionTest {

    private final Solution s = new Solution();

    @MethodSource("testcase")
    @ParameterizedTest
    void test(String[] orders, int[] courses, String[] output) {

        var result = s.solution(orders, courses);
        System.out.println(Arrays.asList(result));
        System.out.println(Arrays.asList(output));

        for (int i = 0; i < output.length; i++) {
            assertEquals(result[i], output[i]);
        }
    }

    private static Stream<Arguments> testcase() {
        return Stream.of(
            Arguments.of(new String[] {"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"}, new int[] {2,3,4}, new String[] {"AC", "ACDE", "BCFG", "CDE"}),
            Arguments.of(new String[] {"ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"},	new int[] {2,3,5}, new String[] {"ACD", "AD", "ADE", "CD", "XYZ"}),
            Arguments.of(new String[] {"XYZ", "XWY", "WXA"}, new int[] {2,3,4}, new String[] {"WX", "XY"})
        );
    }
}