[프로그래머스] 메뉴 리뉴얼 - JAVA 풀이

 

프로그래머스

 

풀이 방법

1. orders에 있는 메뉴들을 오름차순으로 정렬한다.  
   • String 형식이니 char[] 로 변환하여 정렬한 후 다시 String 형식으로 변환
   • 주어진 주문 orders는 문자열로 되어 있다. 메뉴 항목의 순서는 주문마다 다를 수 있기 때문에,
     이를 모두 오름차순으로 정렬하여 같은 메뉴 조합은 항상 같은 문자열이 되도록 통일한다.
2. order에 있는 메뉴들에서 course에 있는 길이 이상이면 combi 메서드를 실행한다
   • course 배열에는 만들고 싶은 메뉴 조합의 길이들이 주어진다.
     각 길이에 대해 다음과 같은 과정을 반복한다.
   • 새로운 map을 생성한다.
     (여기서는 HashMap<String, Integer>를 사용하여, 조합 문자열과 등장 횟수를 저장한다.)
   • 모든 주문을 순회하면서,
     • 만약 주문된 메뉴 수가 현재 course 길이보다 크거나 같으면,
     • combi 메서드를 호출하여 가능한 모든 조합을 만든다.
3. combi에서는 특정길이에 대해 만들수있는 메뉴조합을 모두 만들고 map에 추가한다.
   • combi(String str, StringBuilder sb, int idx, int cnt, int n)는 다음과 같이 동작한다.
     • str: 원본 주문 문자열
     • sb: 현재까지 선택한 메뉴 조합
     • idx: 다음에 탐색할 시작 인덱스
     • cnt: 현재까지 선택한 메뉴 개수
     • n: 목표 메뉴 개수 (course의 값)

• combi는 다음과 같이 재귀적으로 메뉴 조합을 생성한다.
  
  • cnt가 n에 도달하면, sb.toString()을 map에 추가하고, 등장 횟수를 1 증가시킨다.
  • 아직 조합이 완성되지 않았다면,
    • 현재 인덱스 i부터 str.length()까지 반복하며
    • 하나의 문자를 sb에 추가하고, 다음 인덱스(i+1)로 combi를 재귀 호출한다.
    • 호출이 끝나면 sb에서 마지막에 추가한 문자를 삭제하여 이전 상태로 되돌린다.

• for (int i = idx; i < str.length(); i++) 이 부분은, 현재 위치부터 문자열 끝까지의 문자들을 하나씩 선택하는 과정을 나타낸다즉, 현재 인덱스 이후의 문자들 중 하나를 고르고, 다음 문자부터 다시 고르는 식으로 조합을 만든다.

4. map 에 있는 메뉴조합중 개수가 가장 많은 조합의 메뉴수를 구하고 2 이상이면 그 메뉴조합을 answer에 추가

• map에는 만들어진 조합과 그 조합이 등장한 횟수가 저장되어 있다.
  • map을 순회하면서, 등장 횟수 중 가장 높은 값을 max로 저장한다.
  • 다시 map을 순회하면서, 등장 횟수가 max이고, max >= 2인 조합들을 answer에 추가한다.
  최소 2번 이상 주문된 조합만 최종 정답 후보가 된다.

코드

import java.util.*;
import java.util.Map.*;

class Solution {

    static HashMap<String, Integer> map;

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

        for (int i = 0; i < orders.length; i++) { // orders 에 있는 메뉴조합들을 오름차순으로 만듦
            char[] charArr = orders[i].toCharArray();
            Arrays.sort(charArr);
            orders[i] = String.valueOf(charArr);
        }

        for (int i = 0; i < course.length; i++) { // course 길이 만큼 만듦
            map = new HashMap<>();

            int max = Integer.MIN_VALUE;

            for (int j = 0; j < orders.length; j++) {
                StringBuilder sb = new StringBuilder();
                if (course[i] <= orders[j].length()) { // 만약 시킨메뉴들의 길이가 필요길이보다 같거나 크면
                    combi(orders[j], sb, 0, 0, course[i]); // 메뉴조합의 경우의 수를 map에 추가하는 combi
                }
            }

            for (Entry<String, Integer> entry : map.entrySet()) {
                max = Math.max(max, entry.getValue());
            } // 가장 많이 주문된 횟수 max에 저장

            for (Entry<String, Integer> entry : map.entrySet()) {
                if (max >= 2 && entry.getValue() == max) {
                    answer.add(entry.getKey()); // 최소 2번이상 주문된 조합
                }
            }
            Collections.sort(answer);


        }
        return answer;
    }

    public static void combi(String str, StringBuilder sb, int idx, int cnt, int n) {
        if (cnt == n) { // 요리 개수만큼 조합이 완성되면 map에 해당 조합을 넣는다.
            map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) + 1);
            return;
        }

        for (int i = idx; i < str.length(); i++) { 
            sb.append(str.charAt(i));
            combi(str, sb, i + 1, cnt + 1, n);
            sb.delete(cnt, cnt + 1);
        }
    }

}