프로그래머스 : 메뉴 리뉴얼 (Java)

1. 문제링크

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

코딩테스트 연습 - 메뉴 리뉴얼

2. 접근방법

 

2명이상의 손님이 먹을 수 있는 메뉴!

 

메뉴 구성은 2개 코스로 나올 수 있는 모든 요리 수 즉! 조합이다!

 

그리고 그 조합을 가지고

 

"만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다."

 

라는 말이 있기 때문에

 

조합에서 나올 수 있는 명수를 체크하고 같을 경우에는 추가로 담아주는 작업이 필요하다

 

 

문제는 우선 course 배열로 만들 수 있는 조합을 찾아야한다 !!!

 

이후 만들어진 음식 조합이 몇번 나왔는지 체크하고 체크된 수 중 최고값을 찾고 최고값이 2이상이라면 결과값에 더해주는 방식으로 접근하였다.

3. 코드

import java.util.*;
class Solution {
    char maps[], sel[];
	HashMap<Character, String>[] ordersmap;
	int ans, cnt;
	String ansstr;
	List<String> list;

	int calcul(char[] sel) {
		int cnt = 0;
		for (int i = 0; i < ordersmap.length; i++) {
			boolean chk = true;
			for (int j = 0; j < sel.length; j++) {
				if (!ordersmap[i].containsKey(sel[j])) {
					chk = false;
					break;
				}
			}
			if (chk) {
				cnt++;
			}
		}
		return cnt;
	}

	void nCr(int idx, int start, int N, int R) {
		if (idx == R) {
			cnt = calcul(sel);
			if (ans < cnt) {
				ans = cnt;
				list = new ArrayList<String>();
				ansstr = "";
				for (int i = 0; i < sel.length; i++) {
					ansstr += sel[i];
				}
				list.add(ansstr);
			} else if (ans == cnt) {
				ansstr = "";
				for (int i = 0; i < sel.length; i++) {
					ansstr += sel[i];
				}
				list.add(ansstr);
			}
			return;
		}
		for (int i = start; i < N; i++) {
			sel[idx] = maps[i];
			nCr(idx + 1, i + 1, N, R);
		}
	}

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

		HashMap<Character, String> map = new HashMap<>();

		ordersmap = new HashMap[orders.length];

		for (int i = 0; i < orders.length; i++) {
			ordersmap[i] = new HashMap<>();
			for (int j = 0; j < orders[i].length(); j++) {
				map.put(orders[i].charAt(j), "1");
				ordersmap[i].put(orders[i].charAt(j), "1");
			}
		}
		int N = map.size();
		maps = new char[N];
		int index = 0;
		for (char key : map.keySet()) 
			maps[index++] = key;

		String temp[] = new String[100001];
		index = 0;
		for (int i = 0; i < course.length; i++) {
			ans = 0;
			cnt = 0;
			ansstr = "";
			int R = course[i];
			sel = new char[R];
			list = new ArrayList<String>();
			nCr(0, 0, N, R);
			if(ans > 1)
				for (String s : list)
					temp[index++] = s;
		}

		String[] answer = new String[index];
		for (int i = 0; i < index; i++) {
			answer[i] = temp[i];
		}
		Arrays.sort(answer);

		return answer;
	}
}

4. 마치며

역시 카카오... 만만하지 않았다 어려운 녀석이였다.

 

하지만 그 만큼 재미있었던 문제였다.