[코딩테스트] 프로그래머스 72441, 메뉴 리뉴얼

문제

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

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

 

접근

1. 조합을 이용해서 orders 배열에서 course 배열안에 있는 원소값 만큼 뽑습니다.
2. 조합을 통해 나온 코스메뉴 조합을 해시 맵에 넣어 카운팅합니다.
3. 해시 맵에 있는 값중에서 제일 큰 값을 결과 배열에 추가합니다.

코드

public class Solution{
	
	public void combination(char[] arr, boolean[] chosen, int depth, int n, int r, Map<String, Integer> map){
		if(r == 0)
		{
			String result = "";
			for(int i = 0; i < n; i++)
			{
				if(chosen[i])
				{
					result += arr[i];
				}
			}
			
			char[] tempArray = result.toCharArray();
			Arrays.sort(tempArray);
			result = new String(tempArray);
			
			if(map.containsKey(result))
			{
				map.put(result, map.get(result) + 1);
			}
			else
			{
				map.put(result, 1);
			}
			
			return;
		}
		
		if(depth == n)
		{
			return;
		}
		
		// 특정 원소를 포함하고 뽑는 경우
		chosen[depth] = true;
		combination(arr, chosen, depth + 1, n, r - 1, map);
		
		// 특정 원소를 포함하지 않고 뽑는 경우
		chosen[depth] = false;
		combination(arr, chosen, depth + 1, n, r, map);
	}
		
    public String[] solution(String[] orders, int[] course) {
    	List<String> list = new ArrayList<>();
    	String[] answer = null;
    	for(int i = 0; i < course.length; i++)
    	{
    		int maxVal = 0;
        	String result = "";
        	Map<String, Integer> map = new HashMap<String, Integer>();
        	
    		for(String order : orders)
        	{
        		char[] arr = order.toCharArray();
        		int n = arr.length;
        		boolean[] chosen = new boolean[n];
        		combination(arr, chosen, 0, n, course[i], map);	// n개중에서 r개 뽑기	
        	}
    		
        	for(String key : map.keySet())
        	{
        		if(map.get(key) > maxVal)
        		{
        			maxVal = map.get(key);
        		}
        	}
        	for(String key : map.keySet())
        	{
        		if(map.get(key) == maxVal && maxVal >= 2)
        		{
        			list.add(key);
        		}
        	}
    	}
    	list = list.stream().sorted().collect(Collectors.toList());
    	answer = list.toArray(new String[0]);
        return answer;
    }
}

 

References

https://velog.io/@jwisgenius/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV2-%EB%A9%94%EB%89%B4-%EB%A6%AC%EB%89%B4%EC%96%BC