프로그래머스 - 메뉴 리뉴얼

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

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

 

유형

브루트포스, 부분집합

 

문제분석

 

orders의 요소별로 모든 조합의 갯수를 구해줍니다.

 

1번 태스트케이스를 예시로 보면, ABCFG에서 course의 길이가 2, 3, 4니깐 각 길이에 맞는 조합을 모두 구해줍니다.

 

그리고 HashMap자료구조를 통해 {문자열: 갯수} 형태로 넣어줍니다.

 

코드를 보면

현재 인덱스를 선택하고, 인덱스+1로 재귀를 호출함으로써 중복을 막아줍니다.

Map에다가 문자열: 갯수 형태로 저장

 

코스 길이 마다 가장 긴 주문조합을 찾음.

이때, 조건은 2명이상 주문했고, 길이가 2이상이고, 최대값이어야 합니다

 

코드

import java.util.*;
class Solution {
    static int count[];
    static Map<String, Integer> map;
    public String[] solution(String[] orders, int[] course) {
        String[] answer = {};
        map = new HashMap<>();
        count = new int[course.length];
        for(int c=0; c<course.length; c++){
            for(int i=0; i<orders.length; i++){
                char arr[]=orders[i].toCharArray();
                Arrays.sort(arr);
                combine(0, course[c], new String(), arr, c);
            }
        }
        List<String> list = new ArrayList<>();
        for(int c=0; c<course.length; c++){
            for(Map.Entry<String, Integer> m : map.entrySet()){
                if(count[c]>1 && course[c]==m.getKey().length() && m.getValue()==count[c]){
                    list.add(m.getKey());
                }
            }
        }
        Collections.sort(list);
        answer = list.toArray(new String[list.size()]);
        return answer;
    }
    static void combine(int idx, int len,String s, char arr[], int countIdx){
        if(s.length()==len){
            map.put(s, map.getOrDefault(s, 0)+1);
            count[countIdx] = Math.max(count[countIdx], map.get(s));
            return;
        }
        for(int i=idx; i<arr.length; i++) {
        	combine(i+1, len, s+arr[i], arr, countIdx);
        }
    }
}

 

주의할점

조합을 구할때, 약간 헷갈렸다. 조심하자