해당 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/72411
위에 제한사항으로 볼때 시작복잡도는 O(n^2)가 되어도 상관없을듯 하여 백트래킹 기법을 사용해서 무든 주문의 조합을 저장해서 가장 많은 갯수의 조합을 뽑아내는 방식을 생각했다.
private Map<String, Integer> map = new HashMap<>();
public String[] solution(String[] orders, int[] course) {
for (int count : course) {
for (String order : orders) {
if (order.length() >= count) {
// order가 순서가 오름차순이 아니라서 정렬해줌.
char[] chars = order.toCharArray();
Arrays.sort(chars);
order = new String(chars);
// 1. course의 갯수만큼 모든 order의 주문 조합을 뽑아낸다.
DFS(order, "", 0, count);
}
}
}
// 2. 주문 조합이 2개 이상인 조합만 추려낸다.
List<Map.Entry<String, Integer>> list = map.entrySet()
.stream()
.filter(e -> e.getValue() > 1)
.collect(Collectors.toList());
List<String> result = new ArrayList<>();
for (int count : course) {
// 3. course별로 가장 조합이 많은 갯수만 추려낸다.
List<Map.Entry<String, Integer>> countMatchList = list.stream()
.filter(e -> e.getKey().length() == count)
.collect(Collectors.toList());
int max = countMatchList.stream()
.map(Map.Entry::getValue)
.max(Comparator.comparingInt(o -> o))
.orElse(0);
List<String> maxList = countMatchList.stream()
.filter(e -> e.getValue() == max)
.map(Map.Entry::getKey)
.collect(Collectors.toList());
result.addAll(maxList);
}
// 4. 오름차순으로 정렬한다.
Collections.sort(result);
int arrListSize = result.size();
return result.toArray(new String[arrListSize]);
}
public void DFS(String str, String temp, int index, int size) {
if (temp.length() == size) {
int count = map.getOrDefault(temp, 0);
map.put(temp, count + 1);
return;
}
for (int i = index; i < str.length(); i++) {
temp += str.charAt(i);
DFS(str, temp, i + 1, size);
temp = temp.substring(0, temp.length() - 1);
}
}
처음에 떠올렸던 방식은 한 사람의 주문을 다른사람들의 주문과 하나씩 다 비교해가면서 course갯수 만큼 주문한 오더를 찾으려고 했지만 for중첩이 너무 많아지는것같아서 고민을 하던중에 차라리 그냥 모든 조합을 다 저장시키고 제일 많은 조합을 구해보자 라는 생각으로 구현했다. 모든 조합을 다 구현하면 제한사항에 따라서 최악의 기준으로 작동 횟수를 계산해보니 10^2(orders 원소의 최대 크기 * orders 원소의 최대 크기) * 20(orders배열의 최대 크기) * 10(course배열의 최대 크기) = 20000이기 때문에 충분하다고 판단 후 작성했다.