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

문제

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

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

 

풀이

아래와 같은 데이터가 있다. 

알파벳은 각각 메뉴 1개를 의미한다. 

기존 고객들이 주문했던 이력을 바탕으로 코스요리를 구성하려고 한다. 

 

orders: 기존 고객들이 주문 했던 이력

course: 코스요리에 포함시킬 메뉴의 가짓 수

orders	course	result
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]	[2,3,4]	["AC", "ACDE", "BCFG", "CDE"]

고려해야할 중요한 조건이 몇 가지 있다.

 

첫 번째

기존 주문 이력에서 2번 이상 주문된 조합만이 코스 요리 조합의 자격을 갖춘다.

 

예를 들어 AC 조합은 

ABCFG

AC

ACDE

ACDEH

 

주문 이력이 4번 존재하는 조합이다.

따라서 조건 부합

 

두 번째 

특정 가짓수의 코스요리를 구성할 때, 가장 많이 주문된 조합으로 구성한다. 

만약 가장 많이 주문된 조합이 여러 개일 경우 모두 출력한다. 

예를 들어 두 가지 메뉴를 가지는 코스 요리를 구성할 때, 

AC 4번

CD 2번

BC 2번

FG 2번

.... 

AH 1번 (첫 번째 조건에서 탈락)

이렇게 여러 개 조합을 찾을 수 있는데 가장 많이 주문된 AC 조합이 코스요리가 된다.

 

내가 접근한 방법

orders와 course의 최대 크기가 20, 10 이기 때문에 그냥 완전 탐색으로 풀어버렸다.  

 

1. 재귀 함수로 개수에 따른 메뉴 조합을 찾아서 저장한다.

AC, 2

BC, 2

FG, 2

ABC, 3

.... 

이런 식으로 Map에 저장하였다.

    public void recur(String s, String r, int idx, int k){
        if(r.length() == k){
            map.put(r, map.getOrDefault(r, 0) + 1);
            return;
        }
        for(int i = idx; i < s.length(); i++){
            recur(s, r+s.charAt(i), i+1, k);
        }
    }

 

2. 메뉴 가짓수에 따라서 해당하는 조합을 저장한다. 

Stream API 를 사용해 보았다. 만약 c가 3이라면 3개의 메뉴로 구성된 조합이면서 주문 이력이 2번 이상 있는 데이터를 Map에서 찾아서 Menu타입을 담는 리스트를 반환한다. 

            List<Menu> list = map.entrySet().stream()
            .filter(o -> o.getKey().length() == c)
            .filter(o -> o.getValue() >= 2)
            .map(o -> new Menu(o.getKey(), o.getValue()))
            .collect(Collectors.toList());

그리고 list를 주문 이력 횟수 내림차순으로 정렬하여 가장 주문이 많이 된 조합을 저장한다.

(Menu 객체 내 compareTo에 구현)

            Collections.sort(list);
            int max = list.get(0).count;
            for(Menu m : list){
                if(m.count == max) {
                    ans.add(m.name);
                } else {
                    break;
                }
            }

모든 가짓 수에 대한 조합을 저장했다면 

사전 오름차순으로 정렬 한 후, 리턴한다. 

        Collections.sort(ans);
        return ans.stream().toArray(String[]::new);

 

소스코드

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

class Menu implements Comparable<Menu>{
    String name;
    int count;

    public Menu(String name, int count) {
        this.name = name;
        this.count = count;
    }
    
    @Override
    public int compareTo(Menu m){
        return m.count - this.count;
    }
}
class Solution {
    HashMap<String, Integer> map;
    public String[] solution(String[] orders, int[] course) {
        
        map = new HashMap<String, Integer>();
        String r = "";
        for(String order : orders){
            // 정렬
            char[] arr = order.toCharArray();
            Arrays.sort(arr);
            order = "";
            for(char o : arr) {
                order += o;
            }
            // 메뉴 개수에 따른 order 조합 map에 담기
            for(int c : course){
                recur(order, r,  0, c);     
            }
        }
        
        ArrayList<String> ans = new ArrayList<String>();
        for(int c : course){
            List<Menu> list = map.entrySet().stream()
            .filter(o -> o.getKey().length() == c)
            .filter(o -> o.getValue() >= 2)
            .map(o -> new Menu(o.getKey(), o.getValue()))
            .collect(Collectors.toList());
           
            if(list.isEmpty()) continue;
            
            Collections.sort(list);
            int max = list.get(0).count;
            for(Menu m : list){
                if(m.count == max) {
                    ans.add(m.name);
                } else {
                    break;
                }
            }
        }
        
        Collections.sort(ans);
        return ans.stream().toArray(String[]::new);
    }
    
    public void recur(String s, String r, int idx, int k){
        if(r.length() == k){
            map.put(r, map.getOrDefault(r, 0) + 1);
            return;
        }
        for(int i = idx; i < s.length(); i++){
            recur(s, r+s.charAt(i), i+1, k);
        }
    }
}