프로그래머스 Lv.2 메뉴 리뉴얼 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/72411

프로그래머스

 

1. 문제 설명

- 변수

orders : 손님들이 주문한 단품메뉴 문자열

course : 레스토랑의 주인 스카피는 추가하고 싶은 단품메뉴 갯수

 

- 결과

새로 추가하게 될 코스요리의 메뉴 구성

 

- 주의사항

• 결과는 문자열 형식으로 배열에 담아 오름차순으로 정렬
• 배열에 알파벳또한 오름차순으로 정렬
• 가장 많이 주문된 메뉴가 여러 개라면 모두 배열에 담기

 

2. 풀이과정

 

- 알파벳과 코스요리 오름차순으로 정렬

        ArrayList<String> answer = new ArrayList<>();
        ...
        // orders 오름차순 정렬
        for (int i = 0; i < orders.length; i++) {
            char[] c = orders[i].toCharArray();
            Arrays.sort(c);
            orders[i] = String.valueOf(c);
        }
        ...
        // 세트 메뉴얼들 오름차순 정렬
        Collections.sort(answer);
        return answer.toArray(new String[0]);

 

- dfs로 course크기별로 조합 생성 후 map에 저장

        // 원하는 코스갯수 마다 조합 계산
        for (int c : course) {
            map.clear(); // 원하는 코스 갯수마다 map 초기화
            max = 0; // 가장 많이 주문된 횟수 초기화
            
            // 각 메뉴 수에 따른 조합 생성 후 map에 저장
            for (String order : orders) {
                if (order.length() >= c) { // 코스보다 주문이 더 많은 경우
                    dfs(order, c, "", 0, 0);
                }
            }

 

- map에 저장된 가장 많이 주문된 메뉴만 결과에 추가

            // 가장 많이 주문된 횟수 찾기
            for (int count : map.values()) {
                max = Math.max(max, count);
            }

            // 최대횟수인 조합만 결과에 추가
            for (String menu : map.keySet()) {
                if (map.get(menu) == max && max >= 2) {
                    answer.add(menu);
                }
            }

 

- 정해진 코스크기를 기준으로 dfs로 코스 조합 생성

	public void dfs(String order, int c, String str, int count, int index) {
        if (count == c) { // 원하는 코스 수만큼 조합 생성 
            map.put(str, map.getOrDefault(str, 0) + 1); // 완성된 코스조합 및 갯수 추가
            return;
        }
        for (int i = index; i < order.length(); i++) { // 주문을 기준
            String next = str + order.charAt(i);  // 메뉴 추가
            dfs(order, c, next, count + 1, i + 1); 
        }
    }

 

- 전체 코드

import java.util.*;

class Solution {
    public HashMap<String, Integer> map; // 세트 메뉴 횟수 저장
    public int max;

    public String[] solution(String[] orders, int[] course) {
        map = new HashMap<>();
        ArrayList<String> answer = new ArrayList<>();

        // orders 오름차순 정렬
        for (int i = 0; i < orders.length; i++) {
            char[] charArr = orders[i].toCharArray();
            Arrays.sort(charArr);
            orders[i] = String.valueOf(charArr);
        }

        // 원하는 코스갯수 마다 조합 계산
        for (int c : course) {
            map.clear(); // 원하는 코스 갯수마다 map 초기화
            max = 0; // 가장 많이 주문된 횟수 초기화
            
            // 각 메뉴 수에 따른 조합 생성 후 map에 저장
            for (String order : orders) {
                if (order.length() >= c) { // 코스보다 주문이 더 많은 경우
                    dfs(order, c, "", 0, 0);
                }
            }

            // 가장 많이 주문된 횟수 찾기
            for (int count : map.values()) {
                max = Math.max(max, count);
            }

            // 최대횟수인 조합만 결과에 추가
            for (String menu : map.keySet()) {
                if (map.get(menu) == max && max >= 2) {
                    answer.add(menu);
                }
            }
        }

        // 세트 메뉴얼들 오름차순 정렬
        Collections.sort(answer);
        return answer.toArray(new String[0]);
    }

    // dfs로 조합을 생성
	public void dfs(String order, int c, String str, int count, int index) {
        if (count == c) { // 원하는 코스 수만큼 조합 생성 
            map.put(str, map.getOrDefault(str, 0) + 1); // 완성된 코스조합 및 갯수 추가
            return;
        }
        for (int i = index; i < order.length(); i++) { // 주문을 기준
            String next = str + order.charAt(i);  // 메뉴 추가
            dfs(order, c, next, count + 1, i + 1); 
        }
    }
}

 

 

- 다른 분이 푸신 깔끔한 코드

import java.util.*;

class Solution {

    List<String> answerList = new ArrayList<>();
    Map<String, Integer> map = new HashMap<>();

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

        // 1. 각 Order 정렬
        for (int i = 0; i < orders.length; i++) {
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = String.valueOf(arr);
        }

        // 2. 각 order를 기준으로 courseLength 만큼의 조합 만들기
        for (int c : course) {
            for (String order : orders)
                fund("", order, c);

            // 3. 가장 많은 조합 answer에 저장
            if (!map.isEmpty()) {
                List<Integer> countList = new ArrayList<>(map.values());
                int max = Collections.max(countList);

                if (max >= 2)
                    for (String key : map.keySet())
                        if (map.get(key) == max)
                            answerList.add(key);
                map.clear();
            }
        }

        Collections.sort(answerList);
        String[] answer = new String[answerList.size()];
        for (int i = 0; i < answer.length; i++)
            answer[i] = answerList.get(i);

        return answer;
    }

    public void fund(String before, String orders, int count) {
        // 탈출 조건 : count == 0
        if (count == 0) {
            map.put(before, map.getOrDefault(before, 0) + 1);
            return;
        }

        // 0부터 length까지 조합
        for (int i = 0; i < orders.length(); i++)
            String next = before + order.charAt(i);
            fund(next, orders.substring(i + 1), count - 1);
    }
}