완탐 특히 백트래킹 넘 싫다…
틀린거. 그냥 갈아엎어야됨
import java.util.*;
import java.util.stream.*;
class Solution {
private static List<String> ansList = new ArrayList<>();
private static String[] ORDERS;
private static boolean[] visited;
private static int maxCourseLength = -1;
private static Set<Integer> courseSet = new HashSet<>();
public String[] solution(String[] orders, int[] course) {
Arrays.stream(course).forEach((i)->{
maxCourseLength = Math.max(maxCourseLength,i);
courseSet.add(i);
});
visited=new boolean[30];
ORDERS = orders;
solve(0, extractMenus(orders), new ArrayList<>(), 0);
return ansList.toArray(new String[0]);
//A B C D E F G
//메뉴 총 10가지 있다.10C2,3,4,5,6,7,8,*10 충분할듯함.
// 주문한 메뉴들 취합한다.
// 조합을 만들고 각 조합마나다 orders 순회하면서 그 조합이 있는지 확인한다. 이때 조합이 2개이상이면 답중 하나인걸 잊지말고 넣자.
//조합마치고 오름차순 정렬해서 답 리턴한다.
}
private static char[] extractMenus(String[] orders){
Set<Character> set = new HashSet<>();
for(String order : orders){
//Arrays.stream(order.toCharArray()).forEach((c)->set.add(c));
order.chars().forEach(c -> set.add((char) c));
}
char[] arr = new char[set.size()];
int i = 0;
for (char c : set) {
arr[i++] = c;
}
return arr;
}
private static void solve(int depth, char[] menus, List<Character> box, int start){
if(depth <= maxCourseLength){
int count = 0;
for(String order : ORDERS){
boolean success = true;
for(char c : box){
if(!order.contains(String.valueOf(c))){
success = false;
break;
}
}
if(success) count++;
}
if(count >= 2 && courseSet.contains(box.size())){
ansList.add(box.stream().map(String::valueOf).collect(Collectors.joining("")));
}
// return;
}
if(depth == maxCourseLength) return;
for(int i = start ; i < menus.length ; i++){
if(visited[i]) continue;
visited[i] = true;
box.add(menus[i]);
solve(depth + 1, menus, box, i+1);
visited[i] = false;
box.remove(box.size()-1);
}
}
}
import java.util.*;
import java.util.stream.*;
class Solution {
//key: course 길이, value 우선순위큐 코스가 들어가며
private static Map<Integer,PriorityQueue<Course>> map = new HashMap<>();
private static boolean[] visited;
public String[] solution(String[] orders, int[] course) {
//코스 길이별 가장 많이 주문한 것들...
/*
단품메뉴 추출한다.
메뉴들을 조합한다.
조합된 메뉴가 주문에 포홤되는지 확인한다.
그게 2개 이상이면 코스길이, List<String>혹은 우선순위ㅣ큐 맵에 넣어버린다.
완탐 끝내면
맵을 순회하면서 각 리스트에서 스트링가장긴거를 추출한다.
추출한걸 정답 리스트에 넣고 이 리스트에 다 들어갔으면 오름차순으로한다 그리고 리턴시킴!
*/
visited = new boolean[30];
// for(int i=0;i<10;i++){
// map.put(i+1,new PriorityQueue());
// }
for (int c : course) {
map.put(c, new PriorityQueue<Course>());
}
solve(extractMenus(orders),new ArrayList<>(), orders,0);
List<String> ansList = new ArrayList<>();
for(PriorityQueue<Course> pq : map.values()){
int len = -1;
while(!pq.isEmpty()){
Course c = pq.poll();
if(c.count>=len){
len = c.count;
ansList.add(c.value);
}
}
}
ansList.sort(Comparator.naturalOrder());
return ansList.stream().toArray(String[]::new);
}
private static void solve(char[] menus,List<Character> box,String[] orders,int start){
if(box.size() > 0){
int count = 0;
for(String order : orders){
boolean success = true;
for(char menu : box){
if(!order.contains(String.valueOf(menu))){
success = false;
break;
}
}
if(success) count++;
}
if(count >= 2){
map.get(box.size()).add(new Course(box.stream().map(String::valueOf).collect(Collectors.joining("")),count));
}
}
if(box.size() == 10){
return;
}
for(int i=start ; i<menus.length ; i++){
if(visited[i]) continue;
//visited[i] = true;
box.add(menus[i]);
solve(menus, box, orders,i+1);
visited[i] = false;
//box.remove(box.size()-1);
}
}
private static class Course implements Comparable<Course>{
int count = 0;
String value;
Course(String s, int c){
value = s;
count = c;
}
@Override
public int compareTo(Course other){
return other.count - this.count;
}
}
private static char[] extractMenus(String[] orders){
Set<Character> set = new HashSet<>();
for(String order : orders){
order.chars().forEach(i->set.add((char)i));
}
char[] result = new char[set.size()];
int i = 0;
for(char c : set){
result[i++] = c;
}
return result;
}
}
import java.util.*;
import java.util.stream.*;
class Solution {
// key: course 길이, value: 해당 길이의 코스 후보들을 담은 우선순위 큐
private static Map<Integer, PriorityQueue<Course>> map;
public String[] solution(String[] orders, int[] course) {
map = new HashMap<>();
// course 배열에 있는 길이만 map 초기화
for (int c : course) {
map.put(c, new PriorityQueue<>());
}
// 전체 메뉴 모음 추출
char[] menus = extractMenus(orders);
// 조합 생성 시작
solve(menus, new ArrayList<>(), orders, 0);
// 정답 후보 모음
List<String> ansList = new ArrayList<>();
for (int c : course) {
PriorityQueue<Course> pq = map.get(c);
if (pq.isEmpty()) continue;
int max = pq.peek().count; // 가장 많이 나온 조합의 빈도
while (!pq.isEmpty() && pq.peek().count == max) {
ansList.add(pq.poll().value);
}
}
// 사전순 정렬
ansList.sort(Comparator.naturalOrder());
return ansList.toArray(new String[0]);
}
// 조합 생성
private static void solve(char[] menus, List<Character> box, String[] orders, int start) {
if (!box.isEmpty()) {
int count = 0;
for (String order : orders) {
boolean success = true;
for (char menu : box) {
if (!order.contains(String.valueOf(menu))) {
success = false;
break;
}
}
if (success) count++;
}
if (count >= 2 && map.containsKey(box.size())) {
String courseStr = box.stream()
.map(String::valueOf)
.sorted() // 정렬해서 같은 조합이면 동일 문자열로 처리
.collect(Collectors.joining(""));
map.get(box.size()).add(new Course(courseStr, count));
}
}
// 조합 생성 (start부터 시작 → 순열X, 조합O)
for (int i = start; i < menus.length; i++) {
box.add(menus[i]);
solve(menus, box, orders, i + 1);
box.remove(box.size() - 1);
}
}
// Course 클래스
private static class Course implements Comparable<Course> {
int count;
String value;
Course(String s, int c) {
value = s;
count = c;
}
@Override
public int compareTo(Course other) {
if (this.count == other.count) {
return this.value.compareTo(other.value); // count 같으면 문자열 비교
}
return other.count - this.count; // count 내림차순
}
}
// 전체 메뉴 추출
private static char[] extractMenus(String[] orders) {
Set<Character> set = new HashSet<>();
for (String order : orders) {
order.chars().forEach(i -> set.add((char) i));
}
char[] result = new char[set.size()];
int i = 0;
for (char c : set) {
result[i++] = c;
}
return result;
}
}
젬미니가줌
import java.util.*;
import java.util.stream.*;
class Solution {
// key: 조합(코스), value: 주문 횟수
private static Map<String, Integer> combinationMap;
public String[] solution(String[] orders, int[] course) {
// 1. 각 주문을 알파벳 순으로 정렬합니다.
// "BA"와 "AB"는 같은 조합으로 취급해야 하므로 정렬이 필수적입니다.
for (int i = 0; i < orders.length; i++) {
char[] arr = orders[i].toCharArray();
Arrays.sort(arr);
orders[i] = new String(arr);
}
List<String> ansList = new ArrayList<>();
// 2. course 배열에 있는 각 코스 길이에 대해 반복합니다.
for (int c : course) {
combinationMap = new HashMap<>();
// 3. 모든 주문에 대해 해당 길이의 조합을 생성하고 카운트합니다.
for (String order : orders) {
// 만들려는 조합의 길이가 주문 길이보다 길면 스킵
if (order.length() < c) continue;
solve(order, new StringBuilder(), 0, c);
}
// 4. 가장 많이 주문된 조합을 찾습니다.
if (!combinationMap.isEmpty()) {
// 해당 길이의 코스 중 가장 많이 주문된 횟수를 찾습니다.
int max = combinationMap.values().stream()
.max(Comparator.naturalOrder())
.orElse(0);
// 최소 2번 이상 주문된 경우에만 코스로 인정합니다.
if (max >= 2) {
// 가장 많이 주문된 횟수(max)와 동일한 횟수를 가진 모든 조합을 정답 리스트에 추가합니다.
for (String key : combinationMap.keySet()) {
if (combinationMap.get(key) == max) {
ansList.add(key);
}
}
}
}
}
// 5. 최종 결과를 사전순으로 정렬합니다.
ansList.sort(Comparator.naturalOrder());
return ansList.toArray(new String[0]);
}
/**
* 조합을 생성하고 combinationMap에 카운트를 저장하는 메서드
* @param order 현재 처리 중인 정렬된 주문 문자열
* @param box 현재까지 만들어진 조합을 담는 StringBuilder
* @param start 조합을 만들기 위해 탐색을 시작할 인덱스
* @param targetLength 만들고자 하는 조합의 길이
*/
private static void solve(String order, StringBuilder box, int start, int targetLength) {
// 목표 길이에 도달하면, 조합을 map에 저장하고 재귀를 종료합니다.
if (box.length() == targetLength) {
String courseCandidate = box.toString();
combinationMap.put(courseCandidate, combinationMap.getOrDefault(courseCandidate, 0) + 1);
return;
}
// 조합 생성 (start부터 시작)
for (int i = start; i < order.length(); i++) {
box.append(order.charAt(i));
solve(order, box, i + 1, targetLength);
// 백트래킹: 다음 조합을 위해 마지막에 추가한 문자를 제거합니다.
box.deleteCharAt(box.length() - 1);
}
}
// 기존 Course 클래스와 extractMenus 메서드는 새로운 로직에서 더 이상 필요하지 않습니다.
}