문제
핵심
- 입력의 크기가 작아 구현에 초점을 맞춘다.
- 각 손님이 주문한 단품 메뉴가 주어지고, 만들 코스 요리의 단품 메뉴 개수가 주어질 때 손님들이 가장 많이 주문한 단품 메뉴를 고려하여 코스 요리를 구성한다. 메뉴 구성이 여러 개라면 배열에 담아 사전순으로 오름차순 정렬하여 반환해야 한다.
- 먼저, 코스 요리 개수에 맞게 손님들이 주문한 단품 메뉴를 보고 코스 요리 메뉴를 만들어야 한다. 이를 위해 Map자료 구조를 사용할 수 있다.
손님 번호 주문한 단품메뉴 조합
1번 손님 A, B, C, F, G
2번 손님 A, C
요리 2개 코스 A, C -> 1번, 2번 손님으로부터 총 2번 주문
Map<String, Integer> map = new HashMap<>(); // "AC", 1- 단품 메뉴들로 코스 요리를 구성해야 한다. 코스 요리 개수에 따라 만들 수 있는 모든 코스 요리를 모두 구해야하므로 DFS 알고리즘을 적용한다.
void dfs(StringBuilder sb, int digit, int st, char[] chars) {
if (sb.length() == digit) {
map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) + 1);
return;
}
for (int i = st; i < chars.length; ++i) {
sb.append(chars[i]);
dfs(sb, digit, i + 1, chars);
sb.deleteCharAt(sb.length() - 1);
}
}- 단품 메뉴 개수를 기점으로 만들어진 코스 요리 중 가장 인기 있는 코스 요리를 별도로 저장한다. 그 이유는 만들어진 가장 인기 있는 단품 메뉴 개수별 코스 요리 메뉴를 알파벳 오름차순으로 정렬해야 하기 때문이다.
실수했던 부분
- 예제 케이스 3번을 보면, 정답에 "WX"는 존재하지만, 초기 코드에서 이를 잡아내지 못했다. 단순하게 문자열을 뒤집은 것도 순열에 추가하면 되겠다고 생각했다. 뒤집은 문자열도 추가되므로 기존 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보가 된다는 조건을 만족하기 위해
> 1이 아닌> 2조건으로 수정하였다.
void dfs(int depth, String order, int digit, String menu, int st) {
if (depth == digit) {
map.put(menu, map.getOrDefault(menu, 0) + 1);
char[] chars = menu.toCharArray();
Arrays.sort(chars);
String reversed = new String(chars);
if (!menu.equals(reversed)) {
map.put(reversed, map.getOrDefault(reversed, 0) + 1);
}
return;
}
...- 단순히 문자열을 뒤집은 경우만 추가하면 "ABCDE" 코스 요리에서 단순히 "EDCBA"만 추가한다. 같은 메뉴지만 다른 순서인 메뉴("ACBDE" "ABDCE" ...)를 고려하지 못한다.
개선
통과한 초기 코드
import java.util.*;
class Solution {
Map<String, Integer> map = new TreeMap<>();
public String[] solution(String[] orders, int[] course) {
List<Map.Entry<String, Integer>> ans = new ArrayList<>();
for (int i = 0; i < course.length; ++i) {
for (int j = 0; j < orders.length; ++j) {
dfs(0, orders[j], course[i], "", 0);
}
int maxValue = 1;
for (var e : map.entrySet()) {
if (e.getValue() > maxValue) {
maxValue = e.getValue();
}
}
if (maxValue != 1) {
for (var e : map.entrySet()) {
if (e.getValue() == maxValue) {
ans.add(e);
}
}
}
map.clear();
}
ans.sort(Map.Entry.comparingByKey());
List<String> list = new ArrayList<>();
for (var e : ans) {
list.add(e.getKey());
}
String[] answer = list.toArray(new String[0]);
return answer;
}
void dfs(int depth, String order, int digit, String menu, int st) {
if (depth == digit) {
char[] charArray = menu.toCharArray();
Arrays.sort(charArray);
String newMenu = new String(charArray);
map.put(newMenu, map.getOrDefault(newMenu, 0) + 1);
return;
}
for (int i = st; i < order.length(); ++i) {
dfs(depth + 1, order, digit, menu + order.charAt(i), i + 1);
}
}
}1. TreeMap 대신 HashMap 사용
- 처음에 정렬이 필요하다고 생각해서 TreeMap을 사용했었다. 하지만 TreeMap은 키가 정렬된 것이지, Value 크기로 정렬되어 있지는 않다. 두 자료구조 모두 Value를 기준으로 정렬해야 하므로 삽입, 삭제가 O(1)로 동작하는 HashMap을 사용한다.
2. DFS에서 순열 만들 때 StringBuilder 사용
- StringBuilder를 사용하지 않으면 기존 객체에 문자를 이어 붙일 때 새로운 객체를 만드는 비용과 처음부터 복사하는 비용이 추가로 들어간다.
3. 정렬 순서
- 정렬을 만들어진 DFS 종료 조건에서 하면 정렬해야 하는 횟수가 많다. DFS를 시작하기 전에 미리 정렬을 해두면 각 문자열 당 한 번만 정렬해도 된다.
시간복잡도
- : order문자열의 길이 L에서 자릿수(Digit)를 선택하는 조합의 수
코드
import java.util.*;
class Solution {
Map<String, Integer> map = new HashMap<>();
public String[] solution(String[] orders, int[] course) {
List<Map.Entry<String, Integer>> menu = new ArrayList<>();
for (int i = 0; i < course.length; ++i) {
for (int j = 0; j < orders.length; ++j) {
char[] chars = orders[j].toCharArray();
Arrays.sort(chars);
dfs(new StringBuilder(), course[i], 0, chars);
}
int maxValue = 1;
for (var e : map.entrySet()) {
if (e.getValue() > maxValue) {
maxValue = e.getValue();
}
}
if (maxValue != 1) {
for (var e : map.entrySet()) {
if (e.getValue() == maxValue) {
menu.add(e);
}
}
}
map.clear();
}
menu.sort((e1, e2) -> {
return e1.getKey().compareTo(e2.getKey());
});
List<String> ans = new ArrayList<>();
for (var e : menu) {
ans.add(e.getKey());
}
return ans.toArray(new String[0]);
}
void dfs(StringBuilder sb, int digit, int st, char[] chars) {
if (sb.length() == digit) {
map.put(sb.toString(), map.getOrDefault(sb.toString(), 0) + 1);
return;
}
for (int i = st; i < chars.length; ++i) {
sb.append(chars[i]);
dfs(sb, digit, i + 1, chars);
sb.deleteCharAt(sb.length() - 1);
}
}
}
꾸준하게