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

🔒문제

프로그래머스 Lv2. 2021 KAKAO BLIND RECRUITMENT 메뉴 리뉴얼

🔑해결

손님이 주문한 메뉴들의 배열 orders와 구성할 메뉴의 갯수 배열 course가 주어질 때, 조건에 맞는 코스 메뉴 구성 후보를 찾아 문자열 형태로 return 하도록 solution 함수를 작성하는 문제이다.

여기서 조건이란
1. 최소 2가지 이상의 메뉴로 구성된 조합
2. 최소 2명 이상의 손님으로부터 주문된 조합
3. return되는 문자열이 오름차순으로 정렬
이다.

1. 조합 찾기
   1-1. orders에 저장된 문자열을 재귀함수를 사용하여 조합을 찾는다
   1-2. 문자열을 char배열로 바꾸고 Arrays.sort()를 사용해 오름차순으로 정렬한다.(같은 문자 조합이지만 순서가 다를 경우를 방지 ex."XYZ", "XWY", "WXA" -> XW , WX)
   1-3. 조합이 course에 저장된 메뉴의 갯수와 동일하면 저장을 하는데, hashset에 저장하여 중복을 피한다.
2. 찾은 조합을 HashMap<String, Integer>에 저장하여, 조합마다 등장한 횟수를 counting한다.
   2-2. 가장 많은 등장 횟수를 저장할 course배열과 같은 크기의 int배열(c_max)을 생성하여, course배열에 저장된 메뉴의 개수(course[i])와 동일한 조합 길이(count.containKey(iter.next()))를 가진 조합이 c_max[i]에 저장된 값보다 큰 Value값을 가진다면 c_max[i]에 Value값을 저장한다.
3. 최빈 조합 list에 저장
   3-1. HashMap에 저장된 Key값이 course[i]값과 같고 Value값이 c_max[i]값과 같다면, Key값을 list에 저장한다.
4. list를 array로 변환하여 answer배열에 저장
5. answer배열을 오름차순으로 정렬(Arrays.sort())
6. answer배열 반환

🔓코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;

class Solution {
    
    HashSet<String> set;
	int[] n;
    
    public String[] solution(String[] orders, int[] course) {
        String[] answer = {};
        
        HashMap<String, Integer> count = new HashMap<>();
        n = course;
        
        int[] c_max = new int[course.length];

        // 조합 찾기
        for (String order : orders) {
			set = new HashSet<>();
			
			char[] c_order = order.toCharArray();
			Arrays.sort(c_order);
        	find_combi(c_order, 0, "");

        	// 찾은 조합 count에 저장
        	Iterator<String> iter = set.iterator();
        	while(iter.hasNext()) {
        		String tar = iter.next();
        		if (count.containsKey(tar)) {
        			count.put(tar, count.get(tar) + 1);
        		} else {
        			count.put(tar, 1);
        		}
        		
        		for (int i = 0; i < c_max.length; i++) {
					if (tar.length() == course[i]) {
						if (count.get(tar) > c_max[i]) {
							c_max[i] = count.get(tar);
						} else {
							break;
						}
					}
				}
        	}
		}
        
        // 최빈 조합 list에 저장
        ArrayList<String> list = new ArrayList<>();

        for (Entry<String, Integer> entryset : count.entrySet()) {
			for (int i = 0; i < c_max.length; i++) {
				if (entryset.getKey().length() == course[i] && entryset.getValue() == c_max[i] && c_max[i] != 1) {
					list.add(entryset.getKey());
				}
			}
		}
              
        answer = list.toArray(new String[0]);
        // 오름차순 정렬
        Arrays.sort(answer);
        
        return answer;
    }
    
    private void find_combi(char[] c_order, int depth, String combi) {
    	// combi의 length가 course의 수와 일치하면 set에 저장
    	for (int i : n) {
			if (combi.length() == i) {
				set.add(combi);
				break;
			}
		}
    	
    	if (depth == c_order.length) { // depth가 order의 length과 같다면 종료
    		return;
    	} else {
    		
    		find_combi(c_order, depth + 1, combi); //depth번째의 char를 더하지 않은 조합
    		
    		combi = combi.concat(c_order[depth] + ""); // depth번째의 char를 더한 조합
    		find_combi(c_order, depth + 1, combi);
    	}
    }
}