[프로그래머스/JAVA 자바] 메뉴 리뉴얼

 

프로그래머스

문제풀이

1. 조합을 이용. ( ABC에서 두 글자 조합으로 만들때 AB , BA는 같은걸로 취급 )

 

2. hashmap 을 사용하여 orders의 문자열로 만들수 있는 문자열 조합중 course[ ] 에 있는 숫자만큼의 문자열 길이만 조합을 만들어 넣음. 조합을 하기전 orders의 문자열을 알파벳 순으로 정렬을 먼저 진행

ex1 ) course[ ] 가 { 2 , 3 , 4 } 면 2글자 , 3글자 , 4글자 조합만 만들음

ex2 ) orders[ 0 ] 이 "zyx" 이면 알파벳순인 "xyz" 로 정렬 후 진행

 

3. hashmap의 getOrDefalut를 사용하여 손님들이 주문한 요리조합에서 2번 과정을 거친 문자조합을 카운팅

 

4. 카운팅해서 만들어진 hashmap 에서 max 카운팅값의 문자열들만 가져와서 정렬. course 에 2가 있어 요리 2개 코스를 추출하는데 max값이 동일한 코스가 여러개인 경우 모두 추출

나의풀이 ( 코드 )

import java.util.*;

class Solution {
    public String[] solution(String[] orders, int[] course) {
        HashMap<String, Integer> hm = new HashMap<>();
        ArrayList<String> arList = new ArrayList<>();

        for (int i = 0; i < orders.length; i++) {
            char[] charr = orders[i].toCharArray();
            Arrays.sort(charr); // 문자열 정렬


            for (int j = 0; j < course.length; j++) {
                if (charr.length >= course[j]) {
                    List<String> combinations = generateCombinations(String.valueOf(charr), course[j]);

//                     생성된 조합 카운팅
                    for (String combination : combinations) {
                        hm.put(combination, hm.getOrDefault(combination, 0) + 1);
                    }
                }
            }

        }

        ArrayList<String> maxString = new ArrayList<>();

//					max값들 추출
        for (int i = 0; i < course.length; i++) {
            int max = 2;
            for (String z : hm.keySet()) {
                if (hm.get(z) > 1 && z.length() == course[i]) {
                    if (hm.get(z) == max) {
                        maxString.add(z);
                    } else if (hm.get(z) > max) {
                        maxString.clear();
                        maxString.add(z);
                        max = hm.get(z);
                    }
                }
            }

            for (String maxStr : maxString) {
                arList.add(maxStr);
            }
            maxString.clear();
        }


        Collections.sort(arList);

        String[] answer = arList.toArray(new String[0]);
        return answer;
    }
    
    // 문자열에서 길이가 length인 중복되지 않는 모든 가능한 조합을 생성하는 함수
    public static List<String> generateCombinations(String input, int length) {
        List<String> combinations = new ArrayList<>();
        generateCombinationsRecursive(combinations, input, length, "", 0);
        return combinations;
    }

    // 재귀적으로 중복되지 않는 조합을 생성하는 함수
    public static void generateCombinationsRecursive(List<String> combinations, String input, int length, String current, int index) {
        if (current.length() == length) {
            combinations.add(current);
            return;
        }
        for (int i = index; i < input.length(); i++) {
            generateCombinationsRecursive(combinations, input, length, current + input.charAt(i), i + 1);
        }
    }
    
}