[프로그래머스] Lv2. 메뉴 리뉴얼

문제

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

프로그래머스

 

---

풀이

 구현 문제인데, 구현도 구현이지만 자료 구조를 얼마나 잘 이해하고 쓰는지가 중요한 문제라고 생각했습니다.

 

 이 문제를 풀면서, 구현과 시간 초과를 내지 않기 위해 생각했던 중요한 포인트 두 가지는 조합을 구현하는 것과 Map 자료 구조를 사용하는 것이었습니다.

 

 조합을 구현할 때에, 손님을 순차적으로 돌며 손님이 주문한 메뉴 내에서만 조합을 통해 문자열을 찾아내었습니다.

 

 그리고 조합을 통해 나온 문자열이, 다른 손님이 주문한 메뉴에도 있는가? 를 파악하기 위해서 가장 처음에는 하나하나 다시 for문을 돌며 손님과 일치여부를 체크했다가 시간초과가 나는 바람에 생각을 다시 해보니, Map에 문자열을 key 값으로 저장하고 그 key값의 value를 ++ 해주면 되겠다고 생각했습니다.

 

아래는 소스 코드입니다.

---

소스 코드

import java.util.*;

class Solution {
    
    static HashMap<String, Integer> map;
    static int[] courseMax;
    static boolean[] selected;
    static int orderLen;
    static char[] order;
    static ArrayList<String> ans = new ArrayList<>();
    
    public String[] solution(String[] orders, int[] course) {
        String[] answer;
        
        courseMax = new int[course.length];
        map = new HashMap<>();
        
        for(int i = 0; i<orders.length;i++){
            order = orders[i].toCharArray();
            Arrays.sort(order);
            orderLen = order.length;
            
            for(int j = 0; j<course.length;j++){
                selected = new boolean[orderLen];
                comb(0,0,course[j], "", j);
            }
        }
        
        for(String s: map.keySet()){
            for(int j = 0; j<course.length;j++){
               if(courseMax[j]>1&&course[j]==s.length()&&courseMax[j]==map.get(s)){
                   ans.add(s);
               }
            }
        }
        Collections.sort(ans);
        
        answer = new String[ans.size()];
        for(int i = 0; i<ans.size();i++){
            answer[i] = ans.get(i);
        }
        
        return answer;
    }
    
    static void comb(int idx, int cnt, int N, String s, int j){
        if(cnt == N){
            map.put(s, map.containsKey(s)?map.get(s)+1:1);
            courseMax[j] = Math.max(courseMax[j], map.get(s));
        }
        else{
            for(int i = idx; i<orderLen;i++){
                comb(i+1, cnt+1, N, s+order[i], j);
            }
        }
    } 
}