[level2] 프로그래머스 - 메뉴 리뉴얼(JAVA)

전체 코드는 맨 하단에 있습니다.

 

 

[ 문제 풀이 방법 ]

1. 각 손님이 주문한 메뉴(order)를 course개의 조합으로 만들 수 있는 모든 조합을 모두 만듭니다.

2. course[j]개의 조합 중, 가장 많이 선택 받은 수를 max[j]에 저장합니다.

3. 가능한 조합을 담아 둔 menu에서 메뉴 개수가 course[i]개면서 max[i]이고 2번 이상 선택된 메뉴를 담아 리턴합니다.

 

 

 

 

[ 코드 해석 ]

- 채택 될 메뉴의 개수를 아직 모르니, answer을 ArrayList로 선언해줍니다.   
     => 나중에 리턴할 때 array로 바꿉니다.

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

 

- 각 개수별 최대 선택 횟수를 저장할 max배열과
  가능한 모든 메뉴의 조합과 선택 횟수를 저장할 맵인 menu를 선언합니다.

max = new int[course.length];
menu = new HashMap<String, Integer>();

 

- 각 손님이 주문한 메뉴마다 course개의 조합으로 만들 수 있는 모든 조합을 찾아줍니다.
   문제에서   각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.   라고 했으므로 미리 알파벳 순으로 정렬 합니다.
   정렬된 '고객이 선택한 메뉴(order[i])'는 전역변수로 선언된, str에 저장합니다.   => comb에서 사용

for (int i = 0; i < orders.length; i++) {
       // 각 손님이 주문한 메뉴를 알파벳 순으로 정렬
       char a[] = orders[i].toCharArray();
       Arrays.sort(a);
       str = String.copyValueOf(a);     // 문자열로 바꿔서 가지고 있는다.

       // course[j]개의 조합으로 만들 수 있는 모든 조합을 찾는다.
       for (int j = 0; j < course.length; j++) {
              isVisited = new boolean[str.length()];
              comb(0, 0, "", j, course[j]);
       }
}

 

- 조합 함수
   => comb(int cur, int cnt, String s, int j, int N)

int cur : 이제 선택할 문자의 위치(메뉴가 적힌 자리)를 가리킴
int cnt : 현재까지 선택된 메뉴의 개수를 가리킴
String s : 현재까지 선택된 메뉴의 조합
int N : course[]에 해당하는 값, 선택해야 하는 메뉴의 개수

 

 

- N개를 모두 선택 할 때 까지 재귀호출하여, N개 뽑을 수 있는 모든 경우의 수를 구합니다.

 

 

- 구한 경우의 수는 menu에 넣고, 몇 번 선택되었는지 저장합니다.

1번 예제, menu의 일부

 

 

- N(count[j])개를 고르는 경우의 수 중, 가장 많이 선택 된 수를 max[j]에 저장합니다.

private static void comb(int cur, int cnt, String s, int j, int N) {
       if (cnt == N) {
             menu.put(s, menu.containsKey(s) ? menu.get(s) + 1 : 1);
             max[j] = Math.max(max[j], menu.get(s));
             return;
       }

       for (int i = cur; i < str.length(); i++) {
             isVisited[i] = true;
             comb(i + 1, cnt + 1, s + str.charAt(i), j, N);
       }
}

 

- menu에 적힌, 모든 경우의 수 중에서 다음의 모든 것을 만족하는 것을 answer에 넣는다.

1. course[i]개 선택 
          course[i] == s.length()
2. 2번 이상 선택 된 조합
          max[i] != 1
3. course[i]개 선택한 메뉴의 조합 중에서 가장 많이 선택된 것
          menu.get(s) == max[i]

 

- 마지막으로, ArrayList를 String 배열로 바꿔 리턴해준다.

answer.stream().sorted().map(s -> s).toArray(String[]::new);

 

 

 

 

[ 전체 코드 ]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

class Solution {
    static String str;
	static HashMap<String, Integer> menu;
	static boolean isVisited[];
	static int max[];

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

		max = new int[course.length];
		menu = new HashMap<String, Integer>();
		for (int i = 0; i < orders.length; i++) {
			char a[] = orders[i].toCharArray();
			Arrays.sort(a);
			str = String.copyValueOf(a);
			
			for (int j = 0; j < course.length; j++) {
				isVisited = new boolean[str.length()];
				comb(0, 0, "", j, course[j]);
			}
		}

		for (String s : menu.keySet())
			for (int i = 0; i < course.length; i++)
				if (course[i] == s.length() && max[i] != 1 && menu.get(s) == max[i])
					answer.add(s);

		return answer.stream().sorted().map(s -> s).toArray(String[]::new);
	}

	private static void comb(int cur, int cnt, String s, int j, int N) {
		if (cnt == N) {
			menu.put(s, menu.containsKey(s) ? menu.get(s) + 1 : 1);
			max[j] = Math.max(max[j], menu.get(s));
			return;
		}

		for (int i = cur; i < str.length(); i++) {
			isVisited[i] = true;
			comb(i + 1, cnt + 1, s + str.charAt(i), j, N);
		}
	}
}

 

 

혹시
이해가 안 가거나 잘 못 된 것이 있으면,
댓글 부탁드립니다 :)