조합
프로그래머스 2021 KAKAO BLIND RECRUITMENT Level 2 문제 메뉴 리뉴얼을 Java를 이용해 풀어보았다.
가능한 모든 조합을 찾아 저장해야 하는 문제였다. 바로 이거 풀기 전에 외벽 점검 문제를 풀었는데 순열을 적용해서 풀어야 하는 문제였다. 못 풀었다. 근데 바로 또 조합이 나오니까 이건 풀어야겠다 싶어서 끝까지 풀어봤다. 나는 존나 부족하다!
문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/72411
가능한 모든 메뉴 조합 저장하기
문제에서 주어진 String[] orders에 나와있는 메뉴 구성에서 int[] course의 원소 크기만큼의 원소 개수 조합을 찾아줘야 한다. 말로 하니까 어지러운데 그림으로 표현하면 다음과 같다. 
조합을 찾아주기 위해서는 백트래킹을 사용하는데 한 가지 기법을 추가해서 사용한다. nCr 에서 r의 존재를 이용하는 것이다. 재귀를 호출할 때마다 r-1을 넘겨줘서 0이 되면 그때 필요한 개수만큼 다 뽑았다는 의미로 종료해주면 된다. 코드로 살펴보면 다음과 같다.
static void combination(String order, boolean[] visited, int cur, int r){
if(r==0){
String comb = "";
for(int i=0; i<visited.length; i++)
if(visited[i]) comb += order.charAt(i);
if(map.containsKey(comb)) map.put(comb, map.get(comb)+1);
else map.put(comb, 1);
return;
}
for(int i=cur; i<order.length(); i++){
visited[i] = true;
combination(order, visited, i+1, r-1);
visited[i] = false;
}
}r==0에 도달했으면 방문 표시된 메뉴들에 대해서 하나의 문자열을 새로 만들어주고, 그 문자열이 이미 map에 있으면 value를 1 추가해주고 아니면 새롭게 추가해주면 된다.
이런 식으로 모든 orders의 원소들에 대해 조합을 구해주고 나면 모든 조합들과 각각의 출현 횟수를 갖게 된다.
그런데 모든 조합을 찾아주기 위해 combination 메소드를 호출하기 전에 한 가지 해줘야 할 작업이 있다. 모든 orders의 원소들이 알파벳 오름차순으로 정렬된 상태로 combination에 parameter 로 넘겨줘야 하기 때문이다.
그렇지 않으면 XWY와 같은 원소가 들어올 때에, WX 조합이 아닌 XW 조합으로 저장되기 때문에 정보의 왜곡이 생긴다. 이를 위해 하나의 String을 오름차순 정렬해서 반환해줄 메소드를 정의했다.
static String createSortedString(String s){
String res = "";
ArrayList<Character> list = new ArrayList<>();
for(int i=0; i<s.length(); i++)
list.add(s.charAt(i));
Collections.sort(list); // 리스트를 정렬해준 후에
for(char ch: list)
res += ch; // 다시 String으로 만들어주자
return res;
}위의 메소드를 이용해서 문제에서 주어진 orders 배열에 대해 모든 조합을 찾아주는 작업을 코드로 표현하면 다음과 같다.
for(String order: orders){
boolean[] visited = new boolean[order.length()];
for(int i=0; i<course.length; i++)
combination(createSortedString(order), visited, 0, course[i]);
}n개 코스 메뉴 중 가장 많이 나온 녀석 찾기
이 부분은 말로 설명하기가 좀 어려운데(내가 멍청한 건가), int[] course 로 문제에서 주어진 배열은 {2,3,4}일 경우에 2~4개 짜리 코스 조합 중에 가장 많이 나온 녀석들만 추려내야 한다. 그림으로 표현하면 다음과 같다.
그림에 나와있는 조합들이 모든 조합들이라면, 그 중에 빨간색 표시된 녀석들만 정답으로 인정된다는 것이다.
이를 위해서는 HashSet을 이용했다. map의 value값이 최댓값을 갱신할 때마다 set을 초기화해주고 새롭게 추가해준다. 만약 기존 최댓값과 동일한 value를 만나게 되면 그냥 하나 더 추가해주는 거다.
static HashSet<String> set = new HashSet<>();
for(int i=0; i<course.length; i++){ // 각 길이 별로 조사
int length = course[i];
int max = 0;
HashSet<String> tmpSet = new HashSet<>();
for(String key: map.keySet()){
if(key.length()!=length) continue;
if(map.get(key)==max) tmpSet.add(key);
else if(map.get(key)>max && map.get(key)>1){
tmpSet.clear();
tmpSet.add(key);
max = map.get(key);
}
}
set.addAll(tmpSet); // 각 길이별 결과들 set에 추가해주기
}위의 작업을 마치고 나면 set에 우리가 원하는 모든 조합들만 남아있게 된다.
최종 조합 메뉴들 정렬해주기
위에서 set에 나온 모든 녀석들을 그냥 반환하면 또 안 된다. 그 녀석들끼리도 오름차순으로 정렬해줘야 한다. 이를 위해서는 Arrays.sort()를 이용했다.
String[] answer = set.toArray(new String[set.size()]);
Arrays.sort(answer);
return answer;끝!
아래는 내가 제출한 전체 코드다.
import java.util.*;
public class MenuRenew {
static HashMap<String, Integer> map = new HashMap<>();
static HashSet<String> set = new HashSet<>();
static String[] solution(String[] orders, int[] course) {
for(String order: orders){
boolean[] visited = new boolean[order.length()];
for(int i=0; i<course.length; i++)
combination(createSortedString(order), visited, 0, course[i]);
}
for(int i=0; i<course.length; i++){
int length = course[i];
int max = 0;
HashSet<String> tmpSet = new HashSet<>();
for(String key: map.keySet()){
if(key.length()!=length) continue;
if(map.get(key)==max) tmpSet.add(key);
else if(map.get(key)>max && map.get(key)>1){
tmpSet.clear();
tmpSet.add(key);
max = map.get(key);
}
}
set.addAll(tmpSet);
}
String[] answer = set.toArray(new String[set.size()]);
Arrays.sort(answer);
return answer;
}
static void combination(String order, boolean[] visited, int cur, int r){
if(r==0){
String comb = "";
for(int i=0; i<visited.length; i++)
if(visited[i]) comb += order.charAt(i);
if(map.containsKey(comb)) map.put(comb, map.get(comb)+1);
else map.put(comb, 1);
return;
}
for(int i=cur; i<order.length(); i++){
visited[i] = true;
combination(order, visited, i+1, r-1);
visited[i] = false;
}
}
static String createSortedString(String s){
String res = "";
ArrayList<Character> list = new ArrayList<>();
for(int i=0; i<s.length(); i++)
list.add(s.charAt(i));
Collections.sort(list);
for(char ch: list)
res += ch;
return res;
}
public static void main(String[] args) {
String[] orders = {"XYZ", "XWY", "WXA"};
int[] course = {2, 3, 4};
String[] answer = solution(orders, course);
for(String s: answer) System.out.println(s);
}
}오늘 배운 것
조합을 구현할 때는
nCr의r을 활용하자!
2022.03.02 재시도 ( 실패 )
조합을 만들어서 HashMap에 넣고 최대 개수를 가진 메뉴 조합을 반환해야겠다는 생각을 했다. 근데 집중도 너무 안되고... 조합 구현 코드를 짜지 못해서 실패했다. 아이디어를 잘 떠올린 것만으로 만족...할 수 없지만 조합 및 순열 구해주는 코드를 좀 익숙하게 다룰 줄 알아야 겠다.
DFS를 이용해서 조합 만들기!!
- 몇 개 모아야 하는지 (nCr 의 r), 현재까지 몇 개 모았는지
- 현재 몇 번 idx에 위치했는지
- 현재까지 모은 원소들 저장해줄 변수
위의 세 가지를 기본 param으로 넘겨주는 DFS 코드를 짤 줄 알아야 한다!
다음에는 꼭 내 힘으로 풀테야
