안녕하세요. 오늘은 프로그래머스의 메뉴 리뉴얼 문제를 풀어보려고 합니다. 2021년 KAKAO BLIND RECRUITMENT에 출제된 문제입니다.
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/72411
전체 코드
import java.util.*;
class Solution {
public String[] solution(String[] orders, int[] course) {
StringBuilder sb = new StringBuilder();
for(int courseNum : course) {
comList.clear();
for(String order: orders) {
String[] orderSplit = order.split("");
boolean[] visited = new boolean[orderSplit.length];
Arrays.sort(orderSplit);
combination(orderSplit, visited, 0, orderSplit.length, courseNum);
}
/*****comList 결과값 개수 세고, 개수에 따라 sort*****/
Map<String, Integer> map = new HashMap<>();
for (String key : comList) {
map.put(key, map.getOrDefault(key, 0) + 1);
}
List<String> keySetList = new ArrayList<>(map.keySet());
Collections.sort(keySetList, (o1, o2) -> (map.get(o2).compareTo(map.get(o1))));
int maxVal = 0;
for (String key : keySetList) {
if (map.get(key) >= 2) {
if (map.get(key) >= maxVal) {
sb.append(key+",");
maxVal = map.get(key);
}
}
}
}
String[] answer = sb.toString().split(",");
Arrays.sort(answer);
return answer;
}
static ArrayList<String> comList = new ArrayList<>();
//nCr 중복조합, n = orders[i]에 저장된 string의 length/ r = course[i]
//중복조합 함수
static void combination(String[] str, boolean[] visited, int start, int n, int r) {
StringBuilder sb = new StringBuilder();
if (r == 0) {
for (int i = 0; i < visited.length; i++) {
if (visited[i]) {
sb.append(str[i]);
// System.out.print(str[i]+" ");
}
}
comList.add(sb.toString());
sb.delete(0, sb.length());
// System.out.println();
return;
}
for (int i = start; i < n; i++) {
if (visited[i] != true) {
visited[i] = true;
combination(str, visited, i + 1, n, r - 1);
visited[i] = false;
}
}
}
}느낀점
2단계가 맞나 싶을 정도로 어려웠다. 특히 두 가지가 어려웠다.
1) 중복함수 구현
우선 중복조합 함수를 구현하는게 어려웠다. 구현을 어떻게 해야할지 감도 안잡혀서 인터넷을 참고했다..
2) comList에 저장된 결과값 개수 세기
두 번째로 combination함수 이후에 comList에 저장된 결과값의 개수를 세는 것도 어려웠다. 결과값 개수 세는 건 직접 구현해봤지만, 9번 테스트케이스가 계속 틀려서 결국 인터넷을 참고했다. HashMap의 성질을 이용하는 방법은 정말 생각을 못했는데, 기억해둬야겠다.
항상 배열에 저장된 값의 개수 세는 코드 구현해야 할 때 애를 먹었었는데, 이번 기회에 잘 정리해서 완전히 내 것으로 만들어야겠다.
Backend Developer