https://programmers.co.kr/learn/courses/30/lessons/72411
문제
설계
함수에서 받아드리는 INPUT 메뉴들을 원하는 갯수의 Course 조합으로 돌려가며
HashMap에 Combination을 저장해주고,
그 값을 Value기준으로 정렬하여 Max값의 조합을 결과로 Return해주도록 풀었다.
여기서 중요한건 메뉴의 조합이 X,Y 나 Y,X나 똑같은 메뉴조합이기 떄문에, HashMap에 넣어줄때,
반드시 키가되는 String을 정렬해서 넣어줘야한다는점이다 (TestCase 3에서 걸렸습니다.ㅜ)
포인트
1. Combination을 구현할 수 있는지에 대한 물음
2. 다양한 자료구조를 활용할 수 있는지에 대한 물음
3. 해당 자료구조의 정렬과 형변환에 대한 핸들링 (문자열을 문자기준 정렬, HashMap 정렬 등)
풀이
import java.util.*;
class Solution {
public static String[] solution(String[] orders, int[] course) {
ArrayList<String> list = new ArrayList<String>();
HashMap<String, Integer> map = new HashMap<String, Integer>();
for(int combi : course) {
map.clear();
for(String order : orders) {
boolean[] visited = new boolean[order.length()];
combination(map, order, visited, order.length(), 0, combi);
}
List<Map.Entry<String,Integer>> entryset = new LinkedList<>(map.entrySet());
entryset.sort(((o1,o2)-> map.get(o2.getKey())-map.get(o1.getKey())));
int max=2;
for(Map.Entry<String, Integer> entry: entryset) {
if(entry.getValue()>=max) {
list.add(entry.getKey());
max = entry.getValue();
}
}
Collections.sort(list);
}
String[] answer = list.toArray(new String[list.size()]);
return answer;
}
static void combination(HashMap<String,Integer> map,String arr, boolean[] visited, int n, int start, int r) {
if (r == 0) {
String s="";
for(int i=0;i<n;i++) if(visited[i]) s=s.concat(Character.toString(arr.charAt(i)));
char[] chars = s.toCharArray();
Arrays.sort(chars);
s = new String(chars);
map.put(s,map.getOrDefault(s, 0)+1);
return;
}
for (int i = start; i < n; i++) {
visited[i] = true;
combination(map,arr, visited, n, i+1, r-1);
visited[i] = false;
}
}
}
조큼 오래 걸렸다.
Map.Entry에 대한 사용이 점점 많아지고 있다.
HashMap에 객체를 재정렬하는 다양한 방법은 여기를 참조하면 좋은것 같다.
나는 람다 함수식으로 정렬을 통해 내림차순(역순)으로 정렬하였다.
'Algorithm > Weekly Solved' 카테고리의 다른 글
[2021 KAKAO] 순위검색 - Java코드 (0) | 2021.12.06 |
---|---|
[백준 1920] 수찾기 - Java코드 (0) | 2021.12.06 |
[백준 1316] 그룹 단어 체커 - Java 코드 (0) | 2021.11.30 |
[2021 KAKAO] 신규 아이디 추천 - Java코드 (0) | 2021.11.24 |
[백준 2941] 크로아티아 알파벳 - Java 코드 (0) | 2021.11.24 |