[Programmers] 2021 KAKAO BLIND RECRUITMENT - 메뉴 리뉴얼

[작성일]

• 2022-02-10

[분류]

• Map
  
  
  

[문제링크]

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

[요구사항]

• course에 포함되어 있는 세트메뉴 길이를 만족하는 메뉴 중 가장 많이 시킨 것만 담아서 오름차순으로 정답에 담고 출력한다.

[풀이]

1) order를 오름차순으로 정렬해서 입력받는다.

2) 해당 order로 만들 수 있는 세트메뉴를 모두 구한다.

3) 그 세트메뉴를 몇 번 시켰는지 HashMap을 이용해서 저장한다.

4) HashMap을 돌면서 원하는 길이의 세트메뉴 중 가장 많이 시킨 세트메뉴를 answer list에 추가한다.

[코드]

import java.util.*;

class Solution {
    HashMap<String, Integer> hs = new HashMap<>();
    int[] max = new int[11];
    
    public String[] solution(String[] orders, int[] course) {
        // 1. order를 입력받고 나올 수 있는 모든 경우를 조합으로 생성
        for(int i = 0; i < orders.length; i++) {
            char[] orderCharArr = orders[i].toCharArray();
            // order의 문자를 오름차순으로 하기위해서 charArray으로 변환 후 정렬
            Arrays.sort(orderCharArr);
            // 2이상 길이를 가진 메뉴 조합을 생성
            comb(0, "", orderCharArr);
        }
        
        ArrayList<String> answer = new ArrayList<>();
        
        // 2. 메뉴 구성 수가 course에 포함되어 있는 경우에 한해 살펴보기
        for(int i = 0; i < course.length; i++) {
            // hashmap을 순회할 수 있게 iterator로 변경
            Set<String> keys = hs.keySet();
            Iterator<String> iter = keys.iterator();
            
            // hashmap 전체를 순회하면서 가장 많이 주문된 메뉴 구성을 answer에 넣어준다
            while(iter.hasNext()) {
                String order = iter.next();
                if(course[i] == order.length() && hs.get(order) == max[order.length()]) {
                    answer.add(order);
                }
            }
        }
        
        // 사전순 오름차순 정렬
        Collections.sort(answer);
        
        // 정답 출력
        return answer.toArray(new String[answer.size()]);
    }
    
    public void comb(int idx, String set, char[] orders) {
        if(set.length() > 1) {
            // 만들어진 세트메뉴가 hashmap에 없는 경우 새로 추가해주고 해당 메뉴 길이에 대한 주문 횟수를 재설정
            if(!hs.containsKey(set)) {
                hs.put(set, 1);
                if(max[set.length()] == 1) max[set.length()] = 1;
            } else {
                // 기존에 있던 메뉴인 경우 hashmap에 value값을 +1 해준다
                // 해당 메뉴 길이에 대한 주문 횟수를 재설정
                max[set.length()] = Math.max(max[set.length()], hs.get(set) + 1);
                hs.put(set, hs.get(set) + 1);
            }
        }
        
        for(int i = idx; i < orders.length; i++) {
            comb(i + 1, set + "" + orders[i], orders);
        }
    }
}

[통과여부]

[느낀점]

카카오 문제는 역시 쉽지 않고 확실히 그 언어에서 제공하는 것(Iterator 등)들을 능숙하게 쓸 줄 알아야하는 것 같다.