아래와 같은 이유로 시간을 많이 사용함
- 구현하기에는 너무 복잡하다 생각해서 정렬을 통한 묘수가 있을 것이라고 생각했음.
- 문제를 제대로 이해하지 못함.
import java.util.*;
class Solution {
private List<String> answer = new ArrayList<>();
public String[] solution(String[] orders, int[] course) {
sortOrders(orders);
for(int thisCourse : course){
Map<String, Integer> map = new HashMap<>();
// 조합으로 thisCourse개 뽑기
for(String order : orders){
if(thisCourse > order.length())
continue;
combination(map, new StringBuilder(), 0, order, thisCourse);
}
// find max value
int maxValue = Integer.MIN_VALUE;
for(Map.Entry<String, Integer> entry : map.entrySet()){
maxValue = Math.max(maxValue, entry.getValue());
}
if(maxValue <= 1) continue;
//
for(Map.Entry<String, Integer> entry : map.entrySet()){
if(maxValue == entry.getValue()){
answer.add(entry.getKey());
}
}
}
Collections.sort(answer);
return getAnswer();
}
private void sortOrders(String[] orders){
for(int i = 0 ; i < orders.length; i++){
char[] order = orders[i].toCharArray();
Arrays.sort(order);
orders[i] = String.valueOf(order);
System.out.println(orders[i]);
}
System.out.println();
}
private void combination(Map<String, Integer> map, StringBuilder now, int nowIdx, String order, int thisCourse){
if(now.length() == thisCourse){
map.put(now.toString(), map.getOrDefault(now.toString(), 0) + 1);
return;
}
for(int i = nowIdx; i < order.length(); i++){
now.append(order.charAt(i));
combination(map, now, i + 1, order, thisCourse);
now.deleteCharAt(now.length() - 1);
}
}
private String[] getAnswer(){
String[] answerArray = new String[answer.size()];
for(int i = 0 ; i < answer.size(); i++){
answerArray[i] = answer.get(i);
}
return answerArray;
}
}
FLOW
- Map 생성
- orders를 순회하며 course개만큼 조합 뽑기
for(int thisCourse : course){
Map<String, Integer> map = new HashMap<>();
// 조합으로 thisCourse개 뽑기
for(String order : orders){
if(thisCourse > order.length())
continue;
combination(map, new StringBuilder(), 0, order, thisCourse);
}- 생성된 map을 가지고 최대값 찾기
// find max value
int maxValue = Integer.MIN_VALUE;
for(Map.Entry<String, Integer> entry : map.entrySet()){
maxValue = Math.max(maxValue, entry.getValue());
}- 최대값이 2 이상이면 answer 배열에 넣기
if(maxValue <= 1) continue;
for(Map.Entry<String, Integer> entry : map.entrySet()){
if(maxValue == entry.getValue()){
answer.add(entry.getKey());
}
} - 오름차순으로 정렬하기
Collections.sort(answer);Retrospective
- 효율적인 알고리즘이 떠오르지 않으면 일단 구현을 해.. 얍삽하게 공부 ㄴㄴ
To Know List
- char[] to String ⇒ String.valueOf(char[])
- 조합 뽑기 (nowIdx를 인자로 주어 nowIdx부터 for문을 시작하기 ⇒ 이전꺼는 안뽑아줘도 됨)
recursive call 하면서 i + 1로 호출하면 중복 불가능 조합이고, i로 호출하면 중복 가능한 조합임!
private void combination(Map<String, Integer> map, StringBuilder now, int nowIdx, String order, int thisCourse){
if(now.length() == thisCourse){
map.put(now.toString(), map.getOrDefault(now.toString(), 0) + 1);
return;
}
for(int i = nowIdx; i < order.length(); i++){
now.append(order.charAt(i));
combination(map, now, i + 1, order, thisCourse);
now.deleteCharAt(now.length() - 1);
}
}
refactoring version
import java.util.*;
class Solution {
private List<String> answer = new ArrayList<>();
public String[] solution(String[] orders, int[] course) {
sortOrders(orders);
for(int thisCourse : course){
Map<String, Integer> map = new HashMap<>();
// 조합으로 thisCourse개 뽑기
for(String order : orders){
if(thisCourse <= order.length())
combination(map, new StringBuilder(), 0, order, thisCourse);
}
int maxValue = findMaxValue(map);
if(!validateValue(maxValue)){
continue;
}
addAnswer(map, maxValue);
}
Collections.sort(answer);
return getAnswer();
}
private void sortOrders(String[] orders){
for(int i = 0 ; i < orders.length; i++){
char[] order = orders[i].toCharArray();
Arrays.sort(order);
orders[i] = String.valueOf(order);
System.out.println(orders[i]);
}
System.out.println();
}
private void combination(Map<String, Integer> map, StringBuilder now, int nowIdx, String order, int thisCourse){
if(now.length() == thisCourse){
map.put(now.toString(), map.getOrDefault(now.toString(), 0) + 1);
return;
}
for(int i = nowIdx; i < order.length(); i++){
now.append(order.charAt(i));
combination(map, now, i + 1, order, thisCourse);
now.deleteCharAt(now.length() - 1);
}
}
private String[] getAnswer(){
String[] answerArray = new String[answer.size()];
for(int i = 0 ; i < answer.size(); i++){
answerArray[i] = answer.get(i);
}
return answerArray;
}
private int findMaxValue(Map<String, Integer> map){
int maxValue = Integer.MIN_VALUE;
for(Map.Entry<String, Integer> entry : map.entrySet()){
maxValue = Math.max(maxValue, entry.getValue());
}
return maxValue;
}
private boolean validateValue(int maxValue){
return maxValue > 1;
}
private void addAnswer(Map<String, Integer> map, int maxValue){
for(Map.Entry<String, Integer> entry : map.entrySet()){
if(maxValue == entry.getValue()){
answer.add(entry.getKey());
}
}
}
}