[Algorithm/Java] kakao 2021 메뉴 리뉴얼

import java.util.*;

class Solution {
    
    /*
    새로 알아볼 것 : ArrayList, HashMap 라이브러리 사용법 
    sort
    순열, 조합 방식
    map iterator, for each 
    */
    
    private static ArrayList<HashMap<String,Integer>> maps = new ArrayList<>(11);
    
    
    // length길이만큼 만들수 있는 조합 뽑고 MAP에 넣기
    static void perm(char[] chars, int[] visit, int now, int depth, int length){
        if(depth>=2 && depth==length){
            String tmp = "";
            
            //사전순으로 입력해놓기위함 
            int[] str = new int[26];
            for(int i=0; i<chars.length; i++){
                if(visit[i]==1){
                    str[chars[i]-'A']++;
                }
            }
            for(int i=0; i<26; i++){
                if(str[i]!=0)tmp+=(char)(i+'A');
            }

            // 이미 존재한다면 개수를 늘려줌 -> 여기 MAX값으로 나중에 꺼낼 예정 
            if(maps.get(length).isEmpty()){
                maps.get(length).put(tmp,1);
            }
            else if(maps.get(length).containsKey(tmp)){
                int cnt = maps.get(length).get(tmp);
                maps.get(length).replace(tmp, cnt+1);
            }
            else {
                maps.get(length).put(tmp,1);
            }
            return;
        }
        for(int i=now; i<chars.length; i++){
            if(visit[i]==0){
                visit[i]=1;
                perm(chars, visit, i, depth+1, length);
                visit[i]=0;
            }
        }
    }
    
    public String[] solution(String[] orders, int[] course) {
        //초기화 
        maps.clear();
        for(int i=0; i<11 ; i++){
            HashMap<String, Integer> tmp = new HashMap<String, Integer>();
            tmp.put("",0);
            maps.add(tmp);
        }

        // 조합
        for(String order : orders){
            char[] chars = order.toCharArray();
            int[] visit = new int[10];
            for(int i=0; i<10; i++){
                visit[i]=0;
            }
            for(int i=2; i<=chars.length; i++){
                for(int j=0; j<chars.length-1; j++){
                    visit[j]=1;
                    perm(chars, visit, j, 1, i);
                    visit[j]=0;
                }
            }
        }


        // 꺼내서 max 개수 찾고 그 max개수에 맞는 값 가져옴 
        ArrayList<String> ans = new ArrayList<String>();
        int idx = 0;
        for(int c=0; c<course.length; c++){
            int i = course[c];
            if(!maps.get(i).isEmpty()){
                int max=0;
                for(Map.Entry<String, Integer> map : maps.get(i).entrySet()){
                    if(map.getValue()>max ){
                        max = map.getValue();
                    }
                }
                for(Map.Entry<String, Integer> map : maps.get(i).entrySet()){
                    if(max>=2 && map.getValue()==max ){
                        ans.add(map.getKey());
                        idx++;
                    }
                }

            }
        }

        //정렬 
        ans.sort(Comparator.naturalOrder());
        for( String s : ans){
            System.out.println(s);
        }
        String[] answer = ans.toArray(new String[ans.size()]);
        return answer;
    }
}

뭔가 예전에 진짜 풀때 문제 이해도 안되고 틀렸던 기억이있는데..

주먹구구지만 풀려서 기쁘다 >.< 

다른사람들 코드 보면서 공부해야징 

 

 

다시 푼 풀이 22.2.7

시간이게더 줄었음

import java.util.*;
class Solution {
    class Order implements Comparable<Order>{
        String set;
        int cnt;
        Order(String set, int cnt) {
            this.set=set;
            this.cnt=cnt;
        }
        @Override
        public int compareTo(Order o1) {
            return o1.cnt - this.cnt;
        }
    }
    HashMap<String, Integer> map;
    ArrayList<String> results;
    public String[] solution(String[] orders, int[] course) {
        results= new ArrayList<>();
        for(int i=0; i<course.length; i++) {
            permute(orders, course[i]);
        }
        
        Collections.sort(results);
        String[] answer = new String[results.size()];
        for(int i=0; i<results.size(); i++){
            answer[i] = results.get(i);
        }
        return answer;
    }
    
    public void permute(String[] orders, int len) {
        map = new HashMap<>();
        for(int i=0; i<orders.length; i++){
            int [] visit = new int[orders[i].length()];
            if(orders[i].length() < len) continue;
            for(int j=0; j<visit.length; j++) {
                visit[j]=1;
                dfs( j, 1, len, visit, orders[i]);
                visit[j]=0;
            }
        }
        ArrayList<Order> lists = new ArrayList<>();
        for(Map.Entry<String,Integer> entry: map.entrySet()) {
            lists.add(new Order(entry.getKey(), entry.getValue()));
        }
        Collections.sort(lists);
        int maxcnt =0;
        if(lists.size()>0) maxcnt = lists.get(0).cnt;
        if(maxcnt>=2){
            for(Order order : lists) {
                if(order.cnt==maxcnt) results.add(order.set);
                else break;
            }
        }
        
    }
    
    public void dfs(int start, int r, int len, int[] visit, String order) {
        if(r==len) {
            StringBuilder sb = new StringBuilder();
            char[] orderCharArr = order.toCharArray();
            Arrays.sort(orderCharArr);
            for(int i=0; i<visit.length; i++){
                if(visit[i]==1) {
                    sb.append(orderCharArr[i]);
                }
            }
            if(map.containsKey(sb.toString())) {
                map.put(sb.toString(), map.get(sb.toString())+1);
            }
            else {
                map.put(sb.toString(),1);
            }
            return;
        }
        for(int i=start+1; i<visit.length; i++){
            visit[i]=1;
            dfs(i, r+1, len, visit, order);
            visit[i]=0;
        }
    }
    
    
}