[프로그래머스_카카오] 메뉴 리뉴얼
풀이방법
- orders에서 각 order에 대해 모든 조합을 생성한다.
- 각 조합에 대해서는, 해당 조합이 등장한 횟수를 저장한다. (HashMap을 사용한다)
- course에 있는 각 개수만큼의 길이로 이루어진 조합중, 가장 큰 값을 저장한 조합들을 골라내야 한다. 따라서, 각 개수에 대한 HashMap을 생성한다
따라서
1. 하나의 order ->len 을 구한다. -> course에 대해 iterate하면서
- if ( course길이 > len) --> continue
- order에서 course길이의 모든 조합을 생성하여 map.get(course길이)에서 해당 조합이 이미 존재한다면 1을 증가시키고 ,없었다면 새로 추가한다.
- 1에서 생성한 map에는 각 course길이에 대한 조합들이 저장되어있다. LinkedList를 생성하여, 이곳에 정답을 저장한다. (후에 Array로 변환하고, sort를 하여 문제에서 원하는 사전순인 정답을 구하려 한다)
- map.get(course길이) 에 대한 모든 entry를 iterate하며, 가장 최대 값을 갖는 것을 뽑는다.
- 이 때, 문제에서 동일한 값을 갖는다면, 해당 course길이에는 여러개의 조합이 정답이 될 수 있다고 하였다.
- 따라서 기존의 max값과 같은 경우에도 해당 entry를 정답으로 추가한다.
- 이 때 주의할 것은, max값이 업데이트 되는 경우라면, 기존의 max값을 가졌던 entry가 이미 arr에 저장되어있기 때문에 이들을 제거하는 while문이 필요하다.
- LinkedList 인 arr을 Array로 변경한 후, sort 하여 리턴한다
복잡도를 고려하지 않았다 (완탐)
- 문제 해석만 해도 너무 복잡하다.. ㅠ 역시 아직도 잘 못 한다
- 조합을 생성한 것만 봐도, 완전탐색기법으로 풀었다. 단지 시간을 조금 줄이기 위하여 , 각 조합의 개수에 대해 Hash table을 사용하였을 뿐이다.
import java.util.*;
class Solution {
public Map<Integer,Map<String,Integer>> map = new HashMap<>();
public StringBuilder sb = new StringBuilder();
public boolean[] alpha = new boolean['Z'-'A'+1];
public String util = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public String[] solution(String[] orders, int[] course) {
String[] answer = {};
Arrays.sort(orders);
int curlen =0;
// map을 초기화
for(int c:course){
map.put(c,new HashMap<String,Integer>());
}
// 모든 조합을 생성한다
for(String order:orders){
curlen = order.length();
for(int c:course){
// 만들 조합의 길이 > String길이 -> pass
if(curlen<c) continue;
// String으로 조합을 만들기
// 1. alpha setting
initAlpha(order);
// 2. 재귀함수 호출
makeCombi(c,0,-1);
}
}
Deque<String> arr = new LinkedList<>();
// map에는 각 조합에 대한 개수가 저장됨
// map을 iterate 한다
for(int c:course){
int max =0;
// map을 다 iterate하면서....
for(Map.Entry<String, Integer> entry : map.get(c).entrySet()){
int cnt = entry.getValue();
if(cnt<2)continue;
if(cnt<max)continue;
if(cnt>max){
// cnt보다 작은 값을 가졌고, 현재 c와 같은 길이의 String들을 제거 한다.
while(arr.isEmpty()==false){
if(arr.getLast().length()==c){
arr.removeLast();
}
else break;
}
}
max = cnt;
arr.add(entry.getKey());
}
}
answer = new String[arr.size()];
int cur=0;
for(String s:arr){
answer[cur++]=s;
}
Arrays.sort(answer);
return answer;
}
public void initAlpha(String order){
Arrays.fill(alpha,false);
// order의 글자를 setting
for(int i=0;i<order.length();i++)
alpha[order.charAt(i)-'A']=true;
}
public void makeCombi(int c, int cur, int pre){
if(cur==c){
String out = sb.toString();
int numb = map.get(c).getOrDefault(out,0);
map.get(c).put(out,numb+1);
return;
}
for(int i=pre+1;i<'Z'-'A'+1;i++){
if(alpha[i]==false)continue;
sb.append(util.charAt(i));
makeCombi(c,cur+1,i);
sb.deleteCharAt(sb.length()-1);
}
}
}테스트 1 〉 통과 (1.19ms, 67.6MB)
테스트 2 〉 통과 (0.76ms, 61.9MB)
테스트 3 〉 통과 (1.48ms, 72.3MB)
테스트 4 〉 통과 (1.55ms, 71.4MB)
테스트 5 〉 통과 (1.44ms, 72.4MB)
테스트 6 〉 통과 (2.47ms, 76.1MB)
테스트 7 〉 통과 (2.19ms, 61.2MB)
테스트 8 〉 통과 (8.26ms, 73.2MB)
테스트 9 〉 통과 (5.83ms, 60.6MB)
테스트 10 〉 통과 (4.24ms, 80.9MB)
테스트 11 〉 통과 (4.00ms, 73.3MB)
테스트 12 〉 통과 (4.28ms, 75.9MB)
테스트 13 〉 통과 (5.27ms, 74MB)
테스트 14 〉 통과 (6.65ms, 80.3MB)
테스트 15 〉 통과 (6.02ms, 77.1MB)
테스트 16 〉 통과 (4.30ms, 75.8MB)
테스트 17 〉 통과 (4.66ms, 79.7MB)
테스트 18 〉 통과 (4.65ms, 73.6MB)
테스트 19 〉 통과 (3.66ms, 71.8MB)
테스트 20 〉 통과 (7.71ms, 70.5MB)
