[2021 KAKAO] 메뉴 리뉴얼 - Java코드 ★★★

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

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

 

문제

 

설계

함수에서 받아드리는 INPUT 메뉴들을 원하는 갯수의 Course 조합으로 돌려가며

HashMap에 Combination을 저장해주고,   

그 값을 Value기준으로 정렬하여 Max값의 조합을 결과로 Return해주도록 풀었다.

 

여기서 중요한건 메뉴의 조합이 X,Y 나 Y,X나 똑같은 메뉴조합이기 떄문에, HashMap에 넣어줄때,

반드시 키가되는 String을 정렬해서 넣어줘야한다는점이다 (TestCase 3에서 걸렸습니다.ㅜ)

 

포인트

1. Combination을 구현할 수 있는지에 대한 물음

2. 다양한 자료구조를 활용할 수 있는지에 대한 물음

3. 해당 자료구조의 정렬과 형변환에 대한 핸들링 (문자열을 문자기준 정렬, HashMap 정렬 등)

 

풀이

import java.util.*;

class Solution {
	public static String[] solution(String[] orders, int[] course) {
		ArrayList<String> list = new ArrayList<String>();
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		for(int combi : course) {
			map.clear();
			for(String order : orders) {
				boolean[] visited = new boolean[order.length()];
				combination(map, order, visited, order.length(), 0, combi);
			}
			List<Map.Entry<String,Integer>> entryset = new LinkedList<>(map.entrySet());
			entryset.sort(((o1,o2)-> map.get(o2.getKey())-map.get(o1.getKey())));
			int max=2;
			for(Map.Entry<String, Integer> entry: entryset) {
				if(entry.getValue()>=max) {
					list.add(entry.getKey());
					max = entry.getValue();
				}
			}
			Collections.sort(list);
		}	
		String[] answer = list.toArray(new String[list.size()]);
		return answer;
	}
	static void combination(HashMap<String,Integer> map,String arr, boolean[] visited, int n, int start, int r) {
		if (r == 0) {
			String s="";
        	for(int i=0;i<n;i++) if(visited[i]) s=s.concat(Character.toString(arr.charAt(i))); 
        	char[] chars = s.toCharArray();
        	Arrays.sort(chars);
        	s = new String(chars);
        	map.put(s,map.getOrDefault(s, 0)+1);
        	return;
        }
        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(map,arr, visited, n, i+1, r-1);
            visited[i] = false;
        }
    }	
}

 

조큼 오래 걸렸다. 

Map.Entry에 대한 사용이 점점 많아지고 있다.

HashMap에 객체를 재정렬하는 다양한 방법은 여기를 참조하면 좋은것 같다.

나는 람다 함수식으로 정렬을 통해 내림차순(역순)으로 정렬하였다.