[프로그래머스/Level2] 메뉴 리뉴얼

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/72411

문제 접근

해당 문제는 문자열의 조합을 찾아내어 조합별로 나온 개수를 세어 저장하고, 가장 많이 주문된 조합을 찾아 배열로 리턴하면 되는 문제다.

문제를 봤을 때, 조합을 써야하는건 알았지만 조합을 구하는 코드를 몰라 이 부분을 검색하였다.

처음에는 다음과 같이 진행을 했었다.

1. orders에 있는 모든 문자열을 합치고 중복 문자를 제거
2. 합친 문자열의 모든 조합 중 찾으려는 문자 길이의 조합을 구함
3. 나온 조합을 orders를 순회하며 매칭되는 조합의 갯수를 늘림

위와 같이 진행을 하니 시간 초과가 발생하였다...

그래서 다음과 같이 변경하였다.

1. orders를 순회하며 하나의 주문의 모든 조합 중 찾으려는 문자 길이의 조합을 찾음
2. 하나의 주문에서 찾은 조합을 카운팅 진행함

이렇게 바꾸니 통과되었다.

하지만, 생각보다 코드가 길고 메인으로 사용하는 HashMap이 좀 괴랄한 것 같다...

소스 코드

import java.util.*;

class Solution {
    
    public String[] solution(String[] orders, int[] course) {
        //찾을 요리 개수에 대해 나올 수 있는 요리 조합과 해당 요리 조합이 몇번 주문됐는지 카운팅
        HashMap<Integer, HashMap<String, Integer>> patternCountMap = new HashMap<>();
        for (int num : course) {
            patternCountMap.put(num, new HashMap<>());
        }

        for (String order : orders) {
            HashSet<String> patternSet = new HashSet<>(); //조합 중복 제거를 위한 set
            boolean[] visit = new boolean[order.length()];
            combination(order, visit, 0, course, patternSet); //각 주문에 대해 조합을 찾아냄

            //찾은 조합에 대해 카운팅 진행
            for (String pattern : patternSet) {
                HashMap<String, Integer> patternMap = patternCountMap.get(pattern.length());
                if (patternMap.containsKey(pattern)) {
                    patternMap.put(pattern, patternMap.get(pattern) + 1);
                } else {
                    patternMap.put(pattern, 1);
                }
            }
        }

        List<String> maxPatterns = new ArrayList<>(); //가장 많이 주문된 요리 조합을 저장할 리스트
        for (HashMap<String, Integer> patternMap : patternCountMap.values()) {
            //각 가짓 수에 대한 조합 중 최대값을 가져옴
            OptionalInt max = patternMap.values()
                    .stream()
                    .mapToInt(Integer::intValue)
                    .max();

            //최대값이 2 이상이면 해당 값만큼 주문된 조합을 저장함
            if (max.isPresent()) {
                if (max.getAsInt() > 1) {
                    patternMap.keySet()
                            .stream()
                            .filter(key -> patternMap.get(key) == max.getAsInt())
                            .forEach(maxPatterns::add);
                }
            }
        }

        return maxPatterns.stream()
                .sorted()
                .toArray(String[]::new);
    }

    public void combination(String str, boolean[] visit, int depth, int[] course, HashSet<String> patternSet) {
        if (depth != str.length()) {
            visit[depth] = true;
            addString(str, visit, course, patternSet);
            combination(str, visit, depth + 1, course, patternSet);

            visit[depth] = false;
            addString(str, visit, course, patternSet);
            combination(str, visit, depth + 1, course, patternSet);
        }
    }

    public void addString(String str, boolean[] visit, int[] course, HashSet<String> patternSet) {
        String pattern = "";
        for (int i = 0; i < visit.length; i++) {
            if (visit[i]) {
                pattern += str.charAt(i);
            }
        }

        //해당 요리 조합의 문자열 길이가 찾으려는 길이가 맞는지 확인
        if (Arrays.binarySearch(course, pattern.length()) > -1) {
            //맞으면 문자열 정렬 후 set에 저장
            char[] arr = pattern.toCharArray();
            Arrays.sort(arr);
            String sortedPattern = new String(arr);

            patternSet.add(sortedPattern);
        }
    }
}