[Java]프로그래머스 - 메뉴 리뉴얼

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

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

내 코드

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    Map<String, Integer> popular = new HashMap<>();
    List<String> best = new ArrayList<>();

    public String[] solution(String[] orders, int[] course) {
        //비교할 문자열 선정
        for(int i=0; i<orders.length-1; i++){
            for(int j=i+1; j<orders.length; j++){
                //각 문자열 비교
                StringBuilder temp = new StringBuilder();
                for(int k=0; k<orders[i].length(); k++){
                    for(int l=0; l<orders[j].length(); l++){
                        char first = orders[i].charAt(k);
                        char second = orders[j].charAt(l);
                        if(first==second){
                            temp.append(first);
                            break;
                        }
                    }
                }

                for(int c:course){
                    if(c==temp.length()){
                        char[] charArr = temp.toString().toCharArray();
                        Arrays.sort(charArr);
                        String str = String.valueOf(charArr);
                        popular.put(str, popular.getOrDefault(str,0)+1);
                    }
                }
            }
        }
        filterPopular(course);
        Collections.sort(best);
        System.out.println(best);

        return best.stream().toArray(String[]::new);
    }
    private void filterPopular(int[] course){
        for(int c: course){
            Set<String> keys = popular.keySet();
            Map<String, Integer> temp = new HashMap<>();
            for(String key:keys){
                if(key.length()==c){
                    temp.put(key, popular.get(key));
                }
            }
            System.out.println(temp);
            if(!temp.isEmpty()){
                int max = Collections.max(temp.values());
                temp.entrySet().stream()
                    .filter(entry->entry.getValue()==max)
                    .forEach(entry->{
                            best.add(sortCharInString(entry.getKey()));
                        });
            }
        }
    }

    private String sortCharInString(String str){
        char[] charArr = str.toCharArray();
        Arrays.sort(charArr);
        return String.valueOf(charArr);
    }
}

위 코드의 문제점

두 order를 비교할 때 공통적으로 겹치는 경우의 수가 [A,D], [A,D,E]라고 할 때 [A,D]가 묻힌다는 점이다.

해설을 찾아보니 조합메서드를 만들어 모든 경우의 수를 구하고 푸는 것 같다. 참고해서 적용해보자

수정 후 코드

import java.util.*;
import java.util.stream.*;

class Solution {
    private List<String> answer = new ArrayList<>();
    private int[] max;
    private Map<String, Integer> menu = new HashMap<>();

    public String[] solution(String[] orders, int[] course) {
        max = new int[course.length];

        //1. orders내 알파벳 정렬
        for(int i=0; i<orders.length; i++){
            orders[i] = sortOrder(orders[i]);
        }

        //2. order요소별 조합 구해 Map에 저장
        for(int c:course){
            for(int i=0; i<orders.length; i++){
                combi(orders[i], new boolean[orders[i].length()], 0, orders[i].length(), c);
            }
        }

        for(int i=0; i<course.length; i++){
            final int _i=i;
            //3. 길이가 course[i]인 menu중 max를 구함
            menu.entrySet().stream()
                .filter(menu->menu.getKey().length()==course[_i])
                .forEach(filteredMenu -> {
                    max[_i]=Math.max(max[_i], filteredMenu.getValue());
                });

            //4. 길이가 course[i]인 menu중 value==max(가장 많이 주문받은)인 값에 대해 그 key를 List의 저장. 단 1명만 주문한 메뉴는 제외
            menu.entrySet().stream()
                .filter(menu->menu.getKey().length()==course[_i])
                .forEach(filteredMenu -> {
                            if(filteredMenu.getValue()>1&&filteredMenu.getValue()==max[_i]){
                            answer.add(filteredMenu.getKey());
                           }
                });            
        }

        //5. course별 최대 주문 메뉴를 저장한 list를 정렬한 뒤 배열로 반환
        return answer.stream().sorted().toArray(String[]::new);
    }

    private void combi(String order, boolean[] visited, int start, int n, int r){
        if(r==0){
            saveCombi(order, visited, n);
            return;
        }

        for(int i=start; i<n; i++){
            visited[i]=true;
            combi(order, visited, i+1, n, r-1);
            visited[i]=false;
        }
    }

    private void saveCombi(String order, boolean[] visited, int n){
        StringBuilder temp = new StringBuilder();

        for(int i=0; i<n; i++){
            if(visited[i]){
                temp.append(order.charAt(i));
            }
        }
        menu.put(temp.toString(),menu.getOrDefault(temp.toString(), 0)+1);
    }

    private String sortOrder(String order){
        char[] charArr = order.toCharArray();
        Arrays.sort(charArr);
        return String.valueOf(charArr);
    }
}

코드 - 24.02.27

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.*;

class Solution {
    private Map<String, Integer> map = new HashMap<>();
    private List<String> list = new ArrayList<>();

    public String[] solution(String[] orders, int[] course) {
        for(int c : course){
            calcCombi(orders, c);
        }        

        for(int c:course){
            getCourseMenu(c);
        }
        //3. list 오름차순 -> 리턴        
        Collections.sort(list);

        return list.toArray(new String[0]);
    }

        //1. course의 모든 요소에 해당하는 조합을 구함 ex) key(단품 메뉴 조합): ABC, value(주문한 손님 수):2 이때, 2명 이상의 손님이 주문한 단품만 map.add()
    private void calcCombi(String[] orders, int r){
        for(String order: orders){
            recurse(order, r, new boolean[order.length()],0);
        }
    }
    private void recurse(String str, int r, boolean[] visited, int start){
        if(r==0){
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<str.length(); i++){
                if(visited[i]){
                    sb.append(str.charAt(i));
                }
            }
            char[] charArr = sb.toString().toCharArray();
            Arrays.sort(charArr);
            String key = new String(charArr);
            map.put(key, map.getOrDefault(key,0)+1);
            return;
        }

        for(int i=start; i< str.length(); i++){
            if(visited[i]){
                continue;
            }

            visited[i]=true;
            recurse(str, r-1, visited, i+1);
            visited[i]=false;
        }
    }
    //2. 각 course의 요소에 해당하는 길이를 가진 key 집합을 추출하고 가장 큰 조합들을 선별함 -> max value구한 다음 각 조합의 value가 max-value와 같은지 판단. 이후 해당하는 조합만 list.add()
    private void getCourseMenu(int menuSize){
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        Map<String, Integer> _map = new HashMap<>();

        for(Map.Entry<String, Integer> entry: entries){
            if(entry.getKey().length()==menuSize){
                _map.put(entry.getKey(), entry.getValue());
            }
        }

        int max = _map.values().stream().mapToInt(e->e).max().orElse(-1);
        List<String> filtered = _map.entrySet()
            .stream()
            .filter(e->e.getValue()==max&&e.getValue()>1)
            .map(e->e.getKey())
            .collect(Collectors.toList());

        list.addAll(filtered);
    }
}

새로 알게된 점

• Map에서의 stream
  • map.entrySet의 stream사용: 각 요소는 entry타입. getKey(), getValue() 활용
  • map.forEach()사용: 요소는 (k,v)로 받아서 활용 가능
• charArray는 String.valueOf의 매개변수로 넘겨 String으로 만들 수 있다. + new String()도 가능
• stream의 max()메서드는 Optional타입임 get()등으로 벗겨서 사용해야한다.
• map.entrySet()메서드의 리턴 타입은 Set<Map.Entry>이다. Entry는 Map의 내부 클래스이고 새로운 변수로 받을 땐 Set<Map.Entry<keyType, valueType>타입으로 받으면 된다.
• Map타입을 순회할 땐 Map.Entry<keyType, valueType>으로 받으면 된다.
• 어떤 Collection의 요소를 모두 추가하고 싶을 땐 Collection.addAll()메서드를 사용하자.