[프로그래머스] 메뉴 리뉴얼 자바 풀이

문제

https://school.programmers.co.kr/learn/courses/30/lessons/72411?language=java

풀이

소요시간 60분

틀린 풀이

조합을 통해 가능한 전체 코스의 경우의 수를 구하고, 코스가 등장한 갯수를 구하기 위해 map을 이용했다. 이후 map에서 2개 이상 등장 했으며, 코스의 길이가 orders 배열에 포함된 경우 추가하도록 했다.

문제점

코스에 만약 ABCD가 있다면, BCD, CD 와같이 ABCD 내에 포함된 경우를 제거하는 방법을 찾지 못해 풀지 못했다.

새로운 풀이

2개의 코스 요리중 가장 많이 주문한 경우, 3개의 코스 요리중 가장 많이 주문한 경우와 같이 각 코스종류마다 답을 구하도록 수정했다. 풀이를 보고나서 다시 문제를 보니, 이 부분이 중요했다는 사실을 알 수 있었다.

또한, 3번째 입출력 예의 orders 입력을 보면 “WXA”와 같이 정렬되지 않은 상태로 들어오는 데이터가 있는데, 이는 조합을 구할때 문제가 되므로 정렬해주자

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;

class Solution {

    static HashMap<String, Integer> map = new HashMap<>();
    public String[] solution(String[] orders, int[] course) {
        ArrayList<String> arr = new ArrayList<>();
        String[] answer = {};
        for(int i =0;i<orders.length;i++){
            // 2. 각 문자열을 문자형 배열로 변환.
            char[] charArr = orders[i].toCharArray();
            // 3. 해당 문자형 배열을 정렬.
            Arrays.sort(charArr);
            // 4. 정렬된 문자형 배열을 문자열로 변환해 저장.
            orders[i] = String.valueOf(charArr);
        }
        for (int i = 0; i < course.length; i++) {
            map.clear();
            int max = Integer.MIN_VALUE;
            for (int j = 0; j < orders.length; j++) {
                if (course[i] <= orders[j].length()) {
                    String s = orders[j];
                    String res = "";
                    combi(s, res, 0, 0, course[i]);
                }
            }
            for(Entry<String,Integer> entry : map.entrySet()){
                max = Math.max(max,entry.getValue());
            }
            for(Entry<String,Integer> entry : map.entrySet()){
                if(max >=2 && entry.getValue() == max)
                    arr.add(entry.getKey());
            }
        }
        Collections.sort(arr);
        
        return arr.toArray(answer);
    }

    public static void combi(String origin, String result, int idx, int cnt, int n) {
        if (cnt == n) {
            map.put(result, map.getOrDefault(result, 0) + 1);
            return;
        }
        for (int i = idx; i < origin.length(); i++) {
                result += origin.charAt(i);
                combi(origin, result, i+1, cnt+1, n);
                result = result.substring(0, result.length()-1);
            }
    }
}