Java/Java.algorithm
자바(JAVA) - 메뉴 리뉴얼(Programmers : 72411)
자바리안
2022. 3. 15. 00:37
반응형
https://programmers.co.kr/learn/courses/30/lessons/72411
코딩테스트 연습 - 메뉴 리뉴얼
레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서
programmers.co.kr
단순한 String관련 문제인 줄 알았으나,, 각 course 길이의 음식 조합을 카운트 하는 게 핵심인 문제였다.
dfs 기반의 combination 함수를 이용하여 가능한 모든 조합을 구할 수 있었다.
각 코스와 조합된 메뉴의 개수가 동일할 경우 Map에 넣어주며, 중복되는 메뉴들은 value로 카운트 해준 뒤에 value 기준으로 정렬.
정렬된 맵에서 가장 많이 카운트된 조합 + 2명 이상이 주문했는지 확인하며 각 코스에 대한 메뉴 구성을 선택해주면된다.
import java.util.*;
class Solution {
boolean[] visited;
HashMap<String, Integer> countMap;
public String[] solution(String[] orders, int[] course) {
ArrayList<String> answerList = new ArrayList<String>();
for(int c : course) {
countMap = new HashMap<String, Integer>();
for(String order : orders) {
String[] charArr = order.split("");
Arrays.sort(charArr);
visited = new boolean[order.length()];
combination( charArr,0, c);
}
List<Map.Entry<String, Integer>> sortedEntries = new LinkedList<Map.Entry<String, Integer>>(countMap.entrySet());
Collections.sort(sortedEntries, new Comparator<Map.Entry<String,Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
return o2.getValue() - o1.getValue();
}
});
int max = 0;
for(Map.Entry<String, Integer> entry : sortedEntries) {
int count = entry.getValue();
if (count > 1 && count >= max) {
max = count;
answerList.add(entry.getKey());
}
if (max != 0 && entry.getValue() < max) {
break;
}
}
System.out.println(sortedEntries);
System.out.println(answerList);
}
String[] answer = answerList.toArray(new String[answerList.size()]);
Arrays.sort(answer);
return answer;
}
public void combination(String[] arr, int ptr, int r) {
if (r == 0) {
String combStr = "";
for (int i = 0; i < arr.length; i++) {
if (visited[i]) {
combStr += arr[i];
}
}
if (countMap.containsKey(combStr)) {
int count = countMap.get(combStr);
countMap.replace(combStr, count + 1);
} else {
countMap.put(combStr, 1);
}
} else {
for (int i = ptr; i < arr.length; i++) {
if(!visited[i]) {
visited[i] = true;
combination(arr,i + 1, r - 1);
visited[i] = false;
}
}
}
}
}
반응형