문제 링크

문제 간단 해석

단품메뉴 목록에서 정해진 갯수만큼 경우의 수 조합 후 제일 많이 나온 경우의 수들을 알파벳 순서대로 정렬, 출력하는 문제.

Java

풀이 코드

import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Collectors;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public String[] solution(String[] orders, int[] course) {
        Map<Integer, Map<String, Integer>> map = new HashMap<>();
        Map<String, Integer> menuCount;
        char[] charArray;
        StringBuilder sb = new StringBuilder();
        int bitCount;
        String menu;
        List<String> bestMenu = new ArrayList<>();
        
        for (int i: course)
            map.put(i, new HashMap<>());
        
        for (String order: orders) {
            charArray = order.toCharArray();
            Arrays.sort(charArray);
            order = String.valueOf(charArray);
            
            for (int bit = 0; bit < (int)Math.pow(2, order.length()); bit++) {
                bitCount = Integer.bitCount(bit);
                
                if (!map.containsKey(bitCount))
                    continue;
                
                sb.setLength(0);

                for (int j = 0; (bit >> j) > 0; j++)
                    if (((bit >> j) & 1) == 1)
                        sb.append(order.charAt(j));

                menuCount = map.get(bitCount);
                menu = sb.toString();

                if (menuCount.containsKey(menu)) {
                    menuCount.put(menu, menuCount.get(menu) + 1);
                } else {
                    menuCount.put(menu, 1);
                }
            }
        }
        
        for (int i: course) {
            menuCount = map.get(i);
            int maxCount = menuCount.isEmpty() ? 0 : Collections.max(menuCount.values());
            
            if (maxCount <= 1)
                continue;
            
            bestMenu.addAll(
                menuCount.entrySet().stream()
                .filter(entry -> entry.getValue() == maxCount)
                .map(entry -> entry.getKey())
                .collect(Collectors.toList())
            );
        }
        
        String[] answer = bestMenu.toArray(new String[bestMenu.size()]);
        Arrays.sort(answer);
        return answer;
    }
}

해석

Map<Integer, Map<String, Integer>> map = new HashMap<>();
Map<String, Integer> menuCount;
char[] charArray;
StringBuilder sb = new StringBuilder();
int bitCount;
String menu;
List<String> bestMenu = new ArrayList<>();

map의 구조는 N개 코스 -> 메뉴 구성 -> 주문된 횟수이다.

for (int i: course)
    map.put(i, new HashMap<>());

course 값들을 key로 가지게끔 미리 설정해둔다.

for (String order: orders) {
    charArray = order.toCharArray();
    Arrays.sort(charArray);
    order = String.valueOf(charArray);

    ...
}

order를 미리 정렬해 추후 경우의 수 조합 시 순서에 따라 다르게 카운트되는 현상을 방지한다.

for (int bit = 0; bit < (int)Math.pow(2, order.length()); bit++) {
    bitCount = Integer.bitCount(bit);

    if (!map.containsKey(bitCount))
        continue;

    ...
}

bit를 생성, 모든 경우의 수를 확인한다.
이 때, bit의 1 수가 해당 course 내 값인지 아닌지 확인한다.
(course 배열 내에서 찾는 것보다, key로 찾는 게 더 빠르다.)
만약 course 내 값이 아니라면 for문을 이어 돌린다.

sb.setLength(0);

for (int j = 0; (bit >> j) > 0; j++)
    if (((bit >> j) & 1) == 1)
        sb.append(order.charAt(j));

StringBuilder를 초기화하고, 1이 몇 번째 순서에 있는지 j를 통해 확인한다.
확인한 순서에 있는 글자를 조합한다.

menuCount = map.get(bitCount);
menu = sb.toString();

if (menuCount.containsKey(menu)) {
    menuCount.put(menu, menuCount.get(menu) + 1);
} else {
    menuCount.put(menu, 1);
}

조합한 글자를 toString()으로 완성하고, menuCount에 해당 메뉴 조합이 있는지 확인한다.
만약 있다면, 해당 메뉴의 값을 1 늘린다.
없다면, 해당 메뉴를 생성하며 값은 1로 둔다.

for (int i: course) {
    menuCount = map.get(i);
    int maxCount = menuCount.isEmpty() ? 0 : Collections.max(menuCount.values());

    if (maxCount <= 1)
        continue;

    bestMenu.addAll(
        menuCount.entrySet().stream()
        .filter(entry -> entry.getValue() == maxCount)
        .map(entry -> entry.getKey())
        .collect(Collectors.toList())
    );
}

course에 있는 값마다 for문을 돌리며 확인한다.
해당 메뉴들 중에서 가장 최대로 주문된 횟수가 몇인지 확인한다.
만약 menuCount가 비어있다면 에러가 나기 때문에, 비어있을 경우 0으로 카운트한다.

최대로 조합된 메뉴가 1번 이하로 나왔다면, 조건에 맞지 않기에 for문을 이어 돌린다.
최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

menu 중 주문된 횟수가 최대 조합 횟수와 같은 경우만 남긴 후 bestMenu에 추가한다.

String[] answer = bestMenu.toArray(new String[bestMenu.size()]);
Arrays.sort(answer);
return answer;

bestMenu를 String Array로 만든 후 내부 정렬한다. 그 후 반환.

Python

풀이 코드

from itertools import combinations

def solution(orders, course):
    answer = []
    menus = [{} for _ in range(len(course))]
    
    for i in range(len(course)):
        for order in orders:
            if len(order) < course[i]: continue
            order = sorted(list(order))
            
            for menu in list(combinations(order, course[i])):
                try: menus[i][menu] += 1
                except: menus[i][menu] = 1

        best_menus = [menu for menu, cnt in menus[i].items() if max(menus[i].values()) == cnt and cnt > 1]
        for best_menu in best_menus:
            if best_menu:
                answer.append("".join(best_menu))
    
    return sorted(answer)

해석

answer = []
menus = [{} for _ in range(len(course))]

menus 배열 내 dict를 선언한다.

for i in range(len(course)):
    for order in orders:
        if len(order) < course[i]: continue
        order = sorted(list(order))
        
        ...
    ...
return sorted(answer)

course 값과 orders의 값을 하나씩 가져온다.
만약 course 값이 orders 값보다 크다면(해당 order로 조합을 만들 수 없다면) for문을 이어 돌린다.
order를 정렬한다.

for menu in list(combinations(order, course[i])):
    try: menus[i][menu] += 1
    except: menus[i][menu] = 1

해당 주문으로 만들 수 있는 N개의 조합을 모두 추출한다.
해당 메뉴 값이 있다면 1 증가, 없다면 메뉴를 등록하고 1을 넣어준다.

best_menus = [menu for menu, cnt in menus[i].items() if max(menus[i].values()) == cnt and cnt > 1]
    for best_menu in best_menus:
        if best_menu:
            answer.append("".join(best_menu))

해당 메뉴의 주문 횟수가 해당 course에서의 최댓값이며, 2번 이상 주문되었을 경우에 best_menus에 등록되도록 한다.
best_menus 내에 값이 있는 조합들을 하나의 String으로 변경 후 answer에 첨부한다.
그 후 answer 리턴.