프로그래머스 - [Level 2] 메뉴 리뉴얼(JAVA)

프로그래머스 메뉴 리뉴얼[2021 카카오 블라인드]

카테고리 : 완전탐색

[아래 다른 사람의 풀이가 최적화된 풀이인 것 같습니다. 
기록을 위해 포스팅합니다.]

이번 문제는 Lv2 치고는 생각보다 까다로웠다.
PS할 때, C++, JAVASCRIPT만 건드리다가
JAVA로 풀려고하니 쉽지 않았다.
뭔가 자료형을 계속 변환하는 과정이 되게 복잡하다.

풀이 과정은 다음과 같다.

1) 조합을 만든다.
2) 단품메뉴조합을 길이별로 분류하고, 해당 단품메뉴가 몇번 선택되었는지 체크한다.
그리고 단품메뉴를 List에 담는다.
3) List를 돌면서 가장 많이 선택된 메뉴를 answer에 담는다.
4) 오름차순 정렬해주고 answer를 return 한다.

1) 조합

조합은 중복이 되지않고, 순서를 무시하지 않도록 만든다. 경우의 수를 최대한 줄이기 위함이다.

static void recur(int idx,String order){
       
	.
	. 생략
	.
        

for(int i=idx;i<order.length();i++){
	if(visit[i]==1) continue;
	visit[i]=1;
	list.add(order.charAt(i));
	recur(i+1,order);
	list.remove(list.size()-1);
	visit[i]=0;
	}
}

orders 배열이 ["XYZ", "XWY", "WXA"]일 때, list 를 출력해보면 아래와 같다.

"XYZ"
[X, Y]
[X, Y, Z]
[X, Z]
[Y, Z]

"XWY"
[X, W]
[X, W, Y]
[X, Y]
[W, Y]

"WXA"
[W, X]
[W, X, A]
[W, A]
[X, A]

대신, list의 원소들은 매 경우의수 마다 sort 해줘야한다. 문제의 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다. 는 조건 때문이다. sort를 해주지 않으면 [W, X] 의 단품조합은 1개가 나오게된다. 그렇기에"XWY"에서 만들어지는 [X, W] 조합을 [W, X]로 만들어주는 것과 같이 모든 경우의 수의 조합을 정렬해줘야한다.

/*
	이때 새로운 ArrayList를 만들고 sort 해줘야 오류없이 처리된다.
*/

ArrayList<Character> copy_list = new ArrayList<Character>();
copy_list.addAll(list);
copy_list.sort(null);

2) 단품 메뉴 조합 Couting

2) - 1

Map 을 활용해, 단품 메뉴 조합이 몇번 선택되었는지 카운팅해준다. 매번 조합이 만들어 질때마다 아래 과정이 실행된다. 이때, list에 저장된 값을 String으로 변경해 저장해준다.

String combMenu=listToString(copy_list);
if(map.containsKey(combMenu)==false) map.put(combMenu,1);
else
 map.put(combMenu,map.get(combMenu)+1);

맵에 모든 조합을 저장한 뒤 상태는 다음과 같다.

{XY=2, YZ=1, WX=2, XZ=1, WY=1, AWX=1, AW=1, AX=1, XYZ=1, WXY=1}

2) - 2

단품 메뉴 조합을 길이별로 카운팅해준다. 길이별로 가장 많이 선택된 메뉴와 map에 저장된 메뉴의 선택 횟수를 매칭시키기 위함이다.

int len=combMenu.length();
int cnt=map.get(combMenu);
if(count[len]<cnt) count[len]=cnt;

최종 카운트 배열은 다음과 같다.

count[0]=0
count[1]=0
count[2]=2
count[3]=1
count[4]=0

3) answer 만들기

길이별로 가장 많이 선택된 메뉴를 ansewr에 담아준다.

for(int i=0;i<menuList.size();i++){
	int len=menuList.get(i).length();
	if(count[len]<2 || cou.containsKey(len)==false) continue;
	if(count[len]==map.get(menuList.get(i))){
		m.add(menuList.get(i));
		}
	}

소스 코드

import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.*;

class Solution {
    static int[] visit=new int[11];
    static int[] count=new int[11];
    static Map<String,Integer> map=new HashMap<>();
    static Map<Integer,Integer> cou=new HashMap<>();
    static Set<String> set = new HashSet<String>();
    static ArrayList<Character> list = new ArrayList<Character>();
    
    static String listToString(ArrayList<Character> copy_list){
        String str="";
        for(int i=0;i<copy_list.size();i++)
            str+=copy_list.get(i);
        return str;
    }
    
    static void CombMenuCounting(ArrayList<Character> copy_list){
        String combMenu=listToString(copy_list);
        if(map.containsKey(combMenu)==false) map.put(combMenu,1);
        else
            map.put(combMenu,map.get(combMenu)+1);
        
        set.add(combMenu);
        int len=combMenu.length();
        int cnt=map.get(combMenu);
        if(count[len]<cnt) count[len]=cnt;
    }
        
    static void recur(int idx,String order){
        if(list.size()>order.length()) return;
        if(list.size()>1){
          ArrayList<Character> copy_list = new ArrayList<Character>();
          copy_list.addAll(list);
          copy_list.sort(null);
          CombMenuCounting(copy_list);
        }
        
        for(int i=idx;i<order.length();i++){
            if(visit[i]==1) continue;
            visit[i]=1;
            list.add(order.charAt(i));
            recur(i+1,order);
            list.remove(list.size()-1);
            visit[i]=0;
        }
    }
    
    
    public String[] solution(String[] orders, int[] course) {
        for(int i=0;i<course.length;i++)
            cou.put(course[i],1);
        for(int i=0;i<orders.length;i++){
            recur(0,orders[i]);
        }
       
        List<String> menuList = new ArrayList<>(set);
        List<String> m = new ArrayList<>();
        Collections.sort(menuList);
        
        for(int i=0;i<menuList.size();i++){
            int len=menuList.get(i).length();
            if(count[len]<2 || cou.containsKey(len)==false) continue;
            if(count[len]==map.get(menuList.get(i))){
                m.add(menuList.get(i));
            }
        }
        
        String[] answer = new String[m.size()];
        for(int i=0;i<m.size();i++){
            answer[i]=m.get(i);
        }
        Arrays.sort(answer);
       
        return answer;
    }
}

다른 사람의 풀이

우선순위큐를 사용하여 풀이가 훨씬 간단해졌다. 그리고 불필요한 과정을 최소화 하도록 생각을 쉽게해야겠다.

• course 를 활용해 길이별로 조합을 만들어 줬다. 그리고 경우의 수마다 새롭게 map을 생성해줬다.

import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Arrays;
class Solution {
    static HashMap<String,Integer> map;
    static int m;
    public String[] solution(String[] orders, int[] course) {
       PriorityQueue<String> pq = new PriorityQueue<>();
        for (int i=0;i<course.length;i++){
            map = new HashMap<>();
            m=0;
            for (int j=0;j<orders.length;j++) {
                find(0, "", course[i], 0, orders[j]);
            }
            for (String s : map.keySet()){
                if (map.get(s)==m&&m>1){
                    pq.offer(s);
                }
            }
        }
        String  ans[] = new String[pq.size()];
        int k=0;
        while (!pq.isEmpty()){
            ans[k++] = pq.poll();
        }
        return ans;
    }
    static void find(int cnt,String str,int targetNum,int idx,String word){
        if (cnt==targetNum){
            char[] c = str.toCharArray();
            Arrays.sort(c);
            String temps="";
            for (int i=0;i<c.length;i++)temps+=c[i];
            map.put(temps,map.getOrDefault(temps,0)+1);
            m = Math.max(m,map.get(temps));
            return;
        }
        for (int i=idx;i<word.length();i++){
            char now =word.charAt(i);
            find(cnt+1,str+now,targetNum,i+1,word);
        }
    }
}