[프로그래머스/자바] 메뉴 리뉴얼 풀이 - 2021 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2021 KAKAO BLIND RECRUITMENT의 Level 2 문제다.

 

 

동일한 코딩테스트의 Level 2 문제인 순위 검색을 풀고 나니 꽤 비슷하게 느껴져서 빠르게 풀었다.

두 문제 동일하게 주어진 문자열이 가능한 모든 조합을 DFS를 통해 생성한다. 

순위 검색은 이분 탐색을 해서 결과값을 구하지만, 이 문제는 map의 value를 탐색해 결과값을 구하는 것이 다르다. 

 

처음엔 메뉴를 주문한 횟수를 세서 조합하려고 했지만 "손님 한명이 함께 주문한 단품메뉴 조합"이므로

orders의 문자열 각각을 course의 단품메뉴 개수만큼 조합해야 한다.

 

 

orders

["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]

 

course

[2,3,4]

 

 

입출력 예 #1처럼 위와 같은 배열이 들어온다면,

course의 값 2만큼 orders의 메뉴를 조합하고, 가장 많이 주문한 메뉴의 조합을 결과 list에 담는다.

다시 course의 값 3만큼 orders의 메뉴를 조합하고, 가장 많이 주문한 메뉴의 조합을 결과 list에 담으며

course의 length만큼 반복한다.

 

 

 

 

- 배운점 및 느낀점

문제를 이해하면 알고리즘을 생각해내기까지 어렵진 않은데

문제가 뭘 요구하는지 정확히 모르겠고.. 설명 자체를 너무 꼬아서 낸 느낌이다.

2번 이상 주문된 메뉴를 모두 코스요리에 포함하는 것이 아닌,

"가장 많이 함께 주문한 단품메뉴"만 코스요리에 포함하는 것이 중요한 것 같다.

그리고 문자열 하나하나의 값들을 조합하기! 

 

 

import java.util.*;

class Solution {
	static HashMap<String, Integer> map = new HashMap<>();
	static ArrayList<String> result = new ArrayList<>();
	static int max;
	
    public String[] solution(String[] orders, int[] course) {
        // 메뉴 오름차순 정렬
    	for(int i=0;i<orders.length;i++) {
    		char[] c = orders[i].toCharArray();
    		Arrays.sort(c);
    		orders[i] = new String(c);
    	}
    	
    	for(int i=0;i<course.length;i++) {
    		map.clear();
    		max = 0;
    		for(int j=0;j<orders.length;j++) 
    			DFS(orders[j].toCharArray(), 0, course[i], 0, "");
    		
    		findCourse();
    	}
    	
    	String[] ans =  result.toArray(new String[0]);
    	Arrays.sort(ans);
    	
    	return ans;
    }
    
    static void DFS(char[] c, int start, int course, int depth, String s) {
    	if(c.length < course)
    		return;
    	if(depth == course) {
    		// 가장 많이 주문된 메뉴 찾기
    		max = Math.max(max, map.getOrDefault(s, 0) + 1);
    		map.put(s, map.getOrDefault(s, 0) + 1);
    		return;
    	}
    	
    	// 구성할 메뉴의 갯수만큼 조합
    	for(int i=start;i<c.length;i++) 
    		DFS(c, i + 1, course, depth + 1, s + c[i]);
  
    }
    
    // 가장 많이 주문된 메뉴를 결과 List에 저장
    static void findCourse() {
    	if(max < 2)
    		return;
    	
    	for(String s : map.keySet()) {
    		if(map.get(s) == max)
    			result.add(s);
    	}
    }
}