문제
https://school.programmers.co.kr/learn/courses/30/lessons/72411?language=python3
python
from itertools import combinations
def solution(orders, course):
answer = []
cnt_how_many=dict()
for i in course:
cnt_how_many[i]=dict()
for order in orders:
order_list=list(order)
order_list.sort()
for how_many in course:
select_by_how_many=list(combinations(order_list,how_many))
for select in select_by_how_many:
s="".join(select)
if s in cnt_how_many[how_many]:
cnt_how_many[how_many][s]+=1
else:
cnt_how_many[how_many][s]=1
for how_many in course:
largest_list=[]
largest_value=2
for key in cnt_how_many[how_many]:
if cnt_how_many[how_many][key]>largest_value:
largest_value=cnt_how_many[how_many][key]
largest_list=[key]
elif cnt_how_many[how_many][key]==largest_value:
largest_list.append(key)
answer+=largest_list
answer.sort()
return answerjava
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
import java.util.Collections;
import java.util.Arrays;
class Solution {
public static List<String[]> makeCombinations(String[] arr,int n, int r){
List<String[]> combinations=new ArrayList<String[]>();
String[] combination=new String[r];
makeCombination(arr,combination,0,0,r,combinations);
return combinations;
}
public static void makeCombination(String[] arr,String[] combination,int start,int index,int r,List<String[]> combinations){
if(index==r){
combinations.add(combination.clone());
return;
}
for(int i=start;i<=arr.length-r+index;i++){
combination[index]=arr[i];
makeCombination(arr,combination,i+1,index+1,r,combinations);
}
}
public String[] solution(String[] orders, int[] course) {
ArrayList<String> answer = new ArrayList<>();
Map<Integer,Map<String,Integer>> map=new HashMap<>();
for(int how_many : course){
map.put(how_many,new HashMap<String,Integer>());
}
for(String order : orders){
String[] order_list=order.split("");
for(int how_many : course){
List<String[]> combinations=makeCombinations(order_list,order_list.length,how_many);
for(String[] combination : combinations){
Arrays.sort(combination);
StringBuilder sb=new StringBuilder();
for(String k : combination){
sb.append(k);
}
String s=sb.toString();
if(map.get(how_many).containsKey(s)){
map.get(how_many).put(s,map.get(how_many).get(s)+1);
}else{
map.get(how_many).put(s,1);
}
}
}
}
for(int k:course){
int largest_value=2;
ArrayList<String> largest_list=new ArrayList<>();
for(String key : map.get(k).keySet()){
if(largest_value<map.get(k).get(key).intValue()){
largest_value=map.get(k).get(key).intValue();
largest_list=new ArrayList<>();
largest_list.add(key);
}else if(largest_value==map.get(k).get(key).intValue()){
largest_list.add(key);
}
}
for(String s:largest_list){
answer.add(s);
}
}
Collections.sort(answer);
String[] real_answer=answer.toArray(new String[0]);
return real_answer;
}
}내 생각
- python 풀이시간 15분
- java 풀이시간 50분
- 전체적으로 흐름은 이중 map 즉, 딕셔너리를 만들고 크게는 각 선택되는 갯수로 한번 key를 걸고 또 한번은 string으로 걸어서 각 갯수에 나오는 가짓수의 단어가 몇번씩 나오는지 count하는 것이다. 이렇게 count한 다음에 모든 단어를 갯수별로 탐색하면서 갯수당 2회 이상이고 가장 큰 갯수의 단어의 목록을 뽑아서 정답 목록에 추가해주면 된다.
- java의 경우 combinations 즉 조합을 구하는 라이브러리가 따로 없기 때문에, 구현해주어야 하는데 이 때, 재귀를 사용해서 빠르게 구현할 수 있다. 전체적으로 조합을 구하는 함수를 하나 설정해 두고 조합들을 담을 리스트와 현재 구하는 조합을 구하는 리스트를 따로 생성해 둔다. 이를 makeCombination() 함수를 통해 하나씩 만든 후 return 하면 된다.
- makeCombination() 함수를 보면 r이 index와 같을 때, 즉 원하는 가짓수만큼 전부 뽑았을 때, 이를 복사해서 조합들을 담는 리스트에 담아준다. index는 각 조합에서 채워나가는 수이기 때문에 하나씩 combination에 채워나가고 i를 시작점으로 삼아 시작하돼 각 갯수가 뽑힐 때, 중복이 되면 안되므로 전체길이에서 뽑는 수를 빼고 현재 인덱스를 더하는 형태로 제한을 걸어준다.
- 이 외에도, java에 함수가 헷갈려서 몇가지 적으면 Map의 경우 put()으로 넣으며 containsKey로 key의 포함여부를 확인하거나 keySet()으로 모든 키를 호출할 수 있다. 일반 자료형으로 이루어진 배열의 경우는 Arrays를 통해서 정렬가능하며 ArrayList와 같은 리스트의 경우에는 Collections를 통해 정렬하거나 toArray를 통해 일반 자료형의 배열로 형변환 가능하다.
