문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/72411
해당 문제는 문자열의 조합을 찾아내어 조합별로 나온 개수를 세어 저장하고, 가장 많이 주문된 조합을 찾아 배열로 리턴하면 되는 문제다.
문제를 봤을 때, 조합을 써야하는건 알았지만 조합을 구하는 코드를 몰라 이 부분을 검색하였다.
처음에는 다음과 같이 진행을 했었다.
orders
에 있는 모든 문자열을 합치고 중복 문자를 제거orders
를 순회하며 매칭되는 조합의 갯수를 늘림위와 같이 진행을 하니 시간 초과
가 발생하였다...
그래서 다음과 같이 변경하였다.
orders
를 순회하며 하나의 주문의 모든 조합 중 찾으려는 문자 길이의 조합을 찾음이렇게 바꾸니 통과되었다.
하지만, 생각보다 코드가 길고 메인으로 사용하는 HashMap
이 좀 괴랄한 것 같다...
import java.util.*;
class Solution {
public String[] solution(String[] orders, int[] course) {
//찾을 요리 개수에 대해 나올 수 있는 요리 조합과 해당 요리 조합이 몇번 주문됐는지 카운팅
HashMap<Integer, HashMap<String, Integer>> patternCountMap = new HashMap<>();
for (int num : course) {
patternCountMap.put(num, new HashMap<>());
}
for (String order : orders) {
HashSet<String> patternSet = new HashSet<>(); //조합 중복 제거를 위한 set
boolean[] visit = new boolean[order.length()];
combination(order, visit, 0, course, patternSet); //각 주문에 대해 조합을 찾아냄
//찾은 조합에 대해 카운팅 진행
for (String pattern : patternSet) {
HashMap<String, Integer> patternMap = patternCountMap.get(pattern.length());
if (patternMap.containsKey(pattern)) {
patternMap.put(pattern, patternMap.get(pattern) + 1);
} else {
patternMap.put(pattern, 1);
}
}
}
List<String> maxPatterns = new ArrayList<>(); //가장 많이 주문된 요리 조합을 저장할 리스트
for (HashMap<String, Integer> patternMap : patternCountMap.values()) {
//각 가짓 수에 대한 조합 중 최대값을 가져옴
OptionalInt max = patternMap.values()
.stream()
.mapToInt(Integer::intValue)
.max();
//최대값이 2 이상이면 해당 값만큼 주문된 조합을 저장함
if (max.isPresent()) {
if (max.getAsInt() > 1) {
patternMap.keySet()
.stream()
.filter(key -> patternMap.get(key) == max.getAsInt())
.forEach(maxPatterns::add);
}
}
}
return maxPatterns.stream()
.sorted()
.toArray(String[]::new);
}
public void combination(String str, boolean[] visit, int depth, int[] course, HashSet<String> patternSet) {
if (depth != str.length()) {
visit[depth] = true;
addString(str, visit, course, patternSet);
combination(str, visit, depth + 1, course, patternSet);
visit[depth] = false;
addString(str, visit, course, patternSet);
combination(str, visit, depth + 1, course, patternSet);
}
}
public void addString(String str, boolean[] visit, int[] course, HashSet<String> patternSet) {
String pattern = "";
for (int i = 0; i < visit.length; i++) {
if (visit[i]) {
pattern += str.charAt(i);
}
}
//해당 요리 조합의 문자열 길이가 찾으려는 길이가 맞는지 확인
if (Arrays.binarySearch(course, pattern.length()) > -1) {
//맞으면 문자열 정렬 후 set에 저장
char[] arr = pattern.toCharArray();
Arrays.sort(arr);
String sortedPattern = new String(arr);
patternSet.add(sortedPattern);
}
}
}