[알고리즘] 프로그래머스 메뉴 리뉴얼 Java(자바)

- 문제

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

코딩테스트 연습 - 메뉴 리뉴얼

 

- 코드 설명

예제3에서 XWY가 알파벳 순서대로 되어있지 않을 것을 발견 할 수 있습니다.

 

그래서 order를 다시 한번 정렬해주어야합니다.

 

courseMap에는 메뉴 길이별로 order를 모아 놓은 변수 입니다.

 

조합으로 메뉴의 모든 조합을 구하고 메뉴를 시킨 횟수가 높은것 부터 내림차순으로 list를 정렬합니다.

 

이때 시킨횟수가 바뀌면 for문을 종료하고 다음 길이의 메뉴모음으로 이동합니다.

 

마지막으로 메뉴를 String 변수에 " " 단위로 구분해 놓았기때문에

 

answer = str.split(" ") 를 하면 정답을 입력하게 됩니다.

 

다른 분들과 비교했을 때 코드가 깔끔하지 않고 다시 생각해야할 부분들이 보입니다.

 

시간을 내서 다시 저만의 방식으로 나중에 풀어볼 생각입니다.

 

import java.util.*;

class Solution {
    static ArrayList<HashMap<String,Integer>> courseMap;
    
    public String[] solution(String[] orders, int[] course) {
        String[] answer = {};
        String tempAnswer = new String();
        courseMap = new ArrayList<HashMap<String,Integer>>();
        
        
        for(int i=0; i<course.length; i++) courseMap.add(new HashMap<String,Integer>());
        
        for(String order : orders){
            order = sort(order);
            for(int i=0; i<course.length; i++){
                if(order.length() >= course[i]) {
                    boolean[] used = new boolean[order.length()];
                    makeOrder(order, used, new String(), 0,course[i], i);
                }
            }
        }
        
        for(int i=0; i<course.length; i++){
            ArrayList<Map.Entry<String,Integer>> list = new ArrayList<>(courseMap.get(i).entrySet());
            Collections.sort(list, (o1,o2)->  o2.getValue() - o1.getValue());
            
            int maxCount = 0;
            for(Map.Entry<String,Integer> ent : list){
                if(ent.getValue() <2) continue;
                else {
                     maxCount = Math.max(maxCount, ent.getValue());
                    if(maxCount == ent.getValue())
                        tempAnswer = tempAnswer.concat(ent.getKey() + " ");
                }
            }
        }
        
       answer = tempAnswer.split(" ");
       Arrays.sort(answer);
       
        return answer;
    }
    
    static void makeOrder(String order, boolean[] used, String newCourse ,int index, int level, int mapIdx){
        if(level == 0){
            courseMap.get(mapIdx).put(newCourse, courseMap.get(mapIdx).getOrDefault(newCourse,0)+1);
            return;
        }
        
        for(int i=index; i<order.length(); i++){
            if(used[i] == false){
                used[i] = true;
                makeOrder(order, used, newCourse.concat(String.valueOf(order.charAt(i))),i+1, level-1, mapIdx);
                used[i] = false;
            }
        }
    }
    
    static String sort(String str){
        char[] c = str.toCharArray();
        for(int i=0; i<c.length; i++){
            for(int j=i+1; j<c.length; j++){
                if(c[i] > c[j]){
                    char temp = c[j];
                    c[j] = c[i];
                    c[i] = temp;
                }
            }
        }
        return new String(c);
    }
}

 

- 결과