[2021 KAKAO BLIND] 메뉴 리뉴얼 (JAVA)

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

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

풀이법: 

1) courses에서 코스 구성 메뉴 개수 하나 씩 꺼내온다.

2) 각 손님이 시킨 오더 목록마다 코스 메뉴 개수만큼 이루어진 조합 다 구하고 hashmap에 조합 출현횟수 카운팅.

3) 모든 손님 오더 목록 다 돌고 나면 내림차순으로 정렬.

4) 제일 많이 출현한 조합 답 리스트에 추가.

5) courses 다 돌 때까지 1~4 반복.

 

Comment:

HashMap 정렬 생각해서 처음엔 TreeMap 생각했는데 보니까 Key 가 아니라 Value값 기준으로 정렬하는거라 결국 그냥 다 돌아야된다.

 

풀다가 정리가 좀 필요했던 내용:

1) 조합 구현

2) HashMap Value 기준으로 정렬하는 법

 

코드:

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

class Solution {
    static HashMap<String, Integer> hm = new HashMap();
	static ArrayList<String> answer = new ArrayList();

    public String[] solution(String[] orders, int[] course) {
		for(int i = 0 ; i < course.length; i++) {
			
			int r = course[i];
			hm = new HashMap();

			for(int j = 0 ; j < orders.length;j++) {

				String order = orders[j];
				boolean[] visited = new boolean[order.length()];
				combination(order.toCharArray(), visited, 0, order.length(), r);
 			}
			List<Entry<String, Integer>> list = new ArrayList<>(hm.entrySet());
			list.sort(Entry.comparingByValue(Comparator.reverseOrder()));
			list.forEach(System.out::println);

			ArrayList<String> cands = new ArrayList();
			
			if(!list.isEmpty()) {
				Entry<String, Integer> max = list.get(0);
				
				if(max.getValue() >= 2) {
					for(Entry<String, Integer> entry : list) {
						if(entry.getValue() == max.getValue())
							cands.add(entry.getKey());
						else 
							break;
					}
					answer.addAll(cands);
				}
			}
		}
		Collections.sort(answer);
		answer.forEach(System.out::println);
		
		int len = answer.size();
		
		String[] ans = new String[len];
	
		for(int i = 0 ; i < len; i++){
			ans[i] = answer.get(i);
		}
        return ans;
    }
	static void combination(char[] arr, boolean[] visited, int start, int n, int r) {
		if(r == 0) {
			getCourse(arr, visited, n);
		}
		
		for(int i = start; i < n; i++) {
			visited[i] = true;
			combination(arr, visited, i+1, n, r-1);
			visited[i] = false;
		}
	}
	
	static void getCourse(char[] arr, boolean[] visited, int n) {
		StringBuilder sb = new StringBuilder();
		ArrayList<Character> ca = new ArrayList();
		
		for(int i = 0; i < n; i++) {
			if(visited[i]) {
				System.out.print(arr[i] + " ");
				ca.add(arr[i]);
			}
		}
		
		Collections.sort(ca);
		
		for(char c : ca) {
			sb.append(c);
		}
		
		String comb = sb.toString();
		
		if(hm.containsKey(comb)) {
			hm.put(comb, hm.get(comb) + 1);
		}else {
			hm.put(comb, 1);
		}
		System.out.println();
	}


}