![[프로그래머스,Level 2] 메뉴 리뉴얼 (JAVA 구현)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbLnUS3%2FbtqU4YlVf9P%2FOT1Ka124klkefY5MKkcNFk%2Fimg.png)
- 첫 풀이 및 정답풀이
이 문제를 처음 읽고 좀 복잡하여 완벽히 이해할 수 없었다. 문제를 풀기 전에 문제를 이해해보기로 하였다. 우선 문제에서 주어지는 배열은 2가지이다. orders는 문자열 배열로 여러 명의 손님이 주문한 단품 메뉴 정보이다. 입출력 예제 3번의 경우 "XYZ", "XWY", "WXA"가 의미하는 것은 3명의 손님이 존재하며, 첫 번째 손님은 X, Y, Z라는 세 가지 단품 메뉴를, 두 번째 손님은 X, W, Y라는 세 가지 단품 메뉴, 세 번째 손님은 W, X, A라는 세 가지 단품 메뉴를 주문한 것이다.
다음 배열인 course는 코스요리를 구성하는 단품 메뉴의 개수를 의미한다. 입출력 예제 3번에서는 2, 3, 4가 주어졌다. 이는 각각 코스요리에 포함되는 단품 메뉴의 개수가 2개, 3개 4개라는 의미이다. 단, 이 때 코스요리에 포함되기 위한 조건은 서로 다른 사람이 같은 구성의 메뉴를 2개 이상시켜야 한다. 그리고 그 중 가장 많이 시킨 구성의 메뉴를 코스요리로 정한다는 규칙이 존재한다.
"XYZ", "XWY", "WXA" 입출력 예제 3에서 각각의 사람들이 시킨 메뉴들로 코스요리를 구성하기 위해서는 course로 전달받은 정보를 바탕으로 단품 2개의 조합, 단품 3개의 조합, 단품 4개의 조합을 구해야 한다. 단, 이 문제에서는 순열이 아닌, 조합을 요구하기에 X, Y나 Y, X는 같은 조합으로 보는 것에 유의한다.
단품 2개 조합 - 1번 사람 (X,Y/ X, Z/ Y, Z) 2번 사람 (X, W/ X, Y/ W, Y) 3번 사람 (W, X/ W, A / X, A) = 총 9가지
단품 3개 조합 - 1번 사람(X,Y,Z) 2번 사람(X, W, Y) 3번 사람(W, X, A) = 총 3가지
단품 4개 조합 - 세 사람 모두 최대 3개의 메뉴를 시켰으므로 존재하지 않는다.
이렇게 구한 조합에서 코스요리에 들어가기 위한 조건은 최소 2번 등장한 조합 중 최대로 등장한 조합이 된다.
단품 2개 조합의 코스요리 - (X,Y)조합은 1번, 2번이 주문했으므로 2번 등장해 코스요리에 들어갈 수 있다. (W, X)는 2번 사람과 3번 사람이 주문했으므로 2번 등장해 코스요리에 들어갈 수 있다. 나머지 조합은 모두 1번씩 주문되었으며 3번 등장한 조합이 없으므로 COURSE 2의 조합은 (X, Y), (W, X)가 된다.
단품 3개 조합의 코스요리 - (X,Y,Z), (X, W, Y), (W, X, A) 모두 한 번씩만 등장했으므로 COURSE 3의 조합이 가능한 것은 없다.
단품 4개 조합의 코스요리 - 각 사람 모두 최대 3개 주문이 끝이라 4개 조합은 존재할 수 없다.
따라서 최종 코스요리 구성은 (X, Y) (W, X)가 된다.
여기까지가 문제에 대한 이해를 해보았고, 이를 바탕으로 구현해보고자 한다. 구현 순서는 필자가 진행한 순서이다.
1. 최종 반환하는 코스요리 조합에서 각 조합들은 오름차순 정렬이 필요하므로 주어진 orders 배열의 각 문자열들을 오름차순 정렬을 수행한다. 이는 나중에 조합을 구하는 과정에서도 도움이 된다.
// 1. 각 문자열을 오름차순 정렬.
for(int i =0;i<orders.length;i++){
// 2. 각 문자열을 문자형 배열로 변환.
char[] charArr = orders[i].toCharArray();
// 3. 해당 문자형 배열을 정렬.
Arrays.sort(charArr);
// 4. 정렬된 문자형 배열을 문자열로 변환해 저장.
orders[i] = String.valueOf(charArr);
}2. course로 주어지는 각 값을 만들어야 하는 조합의 길이라 생각하면, course의 길이만큼 조합을 구하는 과정이 필요. 위의 예제 3번의 경우와 같이 2, 3, 4는 2 길이의 조합/ 3 길이의 조합/ 4 길이의 조합을 구해야 한다.
// 5. course의 길이만큼 반복하여 필요한 조합을 구함.
for(int i =0;i<course.length;i++){3. 만들어진 조합이 몇명의 사람들에게 주문되었는지 카운트하기 위해서 HashMap 자료구조를 사용하며, 구한 조합들 중 가장 많이 주문된 횟수를 구하기 위한 max변수 사용.
// 5. course의 길이만큼 반복하여 필요한 조합을 구함.
for(int i =0;i<course.length;i++){
// 6. HashMap으로 조합의 수를 카운팅.
map = new HashMap<>();
// 7. course의 경우에 따라 구한 조합들 중 가장 많이 주문된 횟수를 저장.
int max = Integer.MIN_VALUE; 4. 이제 각 사람들의 주문 정보가 담긴 orders 배열을 탐색, 조합을 구하기 위한 메서드 호출. 단, course의 개수 <= 각 문자열의 길이인 경우만 호출한다. 예를 들어, course의 개수가 4개일 때, AB로 구성된 문자열의 길이는 2개이며 2개로는 4개의 조합을 만들 수 없기 때문이다.
// 8. 각 사람들의 조합을 구하기 위해 탐색.
for(int j =0;j<orders.length;j++){
// 9. 조합을 구하기 위해 문자열을 조작할 StringBuilder.
StringBuilder sb = new StringBuilder();
// 10. 코스의 개수 <= 각 문자열의 길이인 경우 조합을 구한다.
if(course[i]<=orders[j].length())
// 11. 조합을 구하기 위한 메소드 호출.
combi(orders[j],sb,0,0,course[i]);
}5. 조합을 구하기 위한 재귀 메소드 작성.
// 12. combi 메소드에서 map에 접근하기 위해 전역변수로 선언.
static HashMap<String,Integer> map;
// 13. 조합을 구하는 메소드 (한 사람의 메뉴구성, 조합을 구할 StringBuilder, 조합을 위한 idx, 코스요리 개수에 따른 종료조건을 위한 cnt와 n)
public static void combi(String str,StringBuilder sb,int idx, int cnt, int n){
// 14. 각 코스요리의 개수만큼 조합이 되면,
if(cnt == n) {
// 15. map에 해당 조합을 삽입 및 카운팅.
map.put(sb.toString(),map.getOrDefault(sb.toString(),0)+1);
return;
}
// 16. idx부터 시작함으로써 조합을 구할 수 있다.
for(int i = idx ; i<str.length();i++){
// 17. sb에 붙여나간다.
sb.append(str.charAt(i));
// 18. 재귀호출.
combi(str,sb,i+1,cnt+1,n);
// 19. 붙였던거 다시 떼기.
sb.delete(cnt,cnt+1);
}
}6. 구한 조합들 중 가장 많이 주문된 횟수를 구한다.
// 20. 가장 많이 주문된 횟수를 max에 저장.
for(Entry<String,Integer> entry : map.entrySet()){
max = Math.max(max,entry.getValue());
}7. max의 값이 최소 2번 이상 주문되었고, 일치하는 경우 해당 key값을 ArrayList에 삽입.
// 21. 최소 2번 이상 주문된 조합이며, 해당 횟수와 일치하는 조합은 ArrayList에 삽입.
for(Entry<String,Integer> entry : map.entrySet()){
if(max >=2 && entry.getValue() == max)
answer.add(entry.getKey());
}8. 마지막으로 ArrayList에 삽입된 조합들을 오름차순으로 정렬하면 끝.
// 22. 추가된 조합들을 오름차순 정렬.
Collections.sort(answer);아래는 전체 코드이다.
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Collection;
import java.util.Collections;
import java.util.ArrayList;
class Solution {
// 12. combi 메소드에서 map에 접근하기 위해 전역변수로 선언.
static HashMap<String,Integer> map;
// 13. 조합을 구하는 메소드 (한 사람의 메뉴구성, 조합을 구할 StringBuilder, 조합을 위한 idx, 코스요리 개수에 따른 종료조건을 위한 cnt와 n)
public static void combi(String str,StringBuilder sb,int idx, int cnt, int n){
// 14. 각 코스요리의 개수만큼 조합이 되면,
if(cnt == n) {
// 15. map에 해당 조합을 삽입 및 카운팅.
map.put(sb.toString(),map.getOrDefault(sb.toString(),0)+1);
return;
}
// 16. idx부터 시작함으로써 조합을 구할 수 있다.
for(int i = idx ; i<str.length();i++){
// 17. sb에 붙여나간다.
sb.append(str.charAt(i));
// 18. 재귀호출.
combi(str,sb,i+1,cnt+1,n);
// 19. 붙였던거 다시 떼기.
sb.delete(cnt,cnt+1);
}
}
public ArrayList<String> solution(String[] orders, int[] course) {
ArrayList<String> answer = new ArrayList<>();
// 1. 각 문자열을 오름차순 정렬.
for(int i =0;i<orders.length;i++){
// 2. 각 문자열을 문자형 배열로 변환.
char[] charArr = orders[i].toCharArray();
// 3. 해당 문자형 배열을 정렬.
Arrays.sort(charArr);
// 4. 정렬된 문자형 배열을 문자열로 변환해 저장.
orders[i] = String.valueOf(charArr);
}
// 5. course의 길이만큼 반복하여 필요한 조합을 구함.
for(int i =0;i<course.length;i++){
// 6. HashMap으로 조합의 수를 카운팅.
map = new HashMap<>();
// 7. course의 경우에 따라 구한 조합들 중 가장 많이 주문된 횟수를 저장.
int max = Integer.MIN_VALUE;
// 8. 각 사람들의 조합을 구하기 위해 탐색.
for(int j =0;j<orders.length;j++){
// 9. 조합을 구하기 위해 문자열을 조작할 StringBuilder.
StringBuilder sb = new StringBuilder();
// 10. 코스의 개수 <= 각 문자열의 길이인 경우 조합을 구한다.
if(course[i]<=orders[j].length())
// 11. 조합을 구하기 위한 메소드 호출
combi(orders[j],sb,0,0,course[i]);
}
// 20. 가장 많이 주문된 횟수를 max에 저장.
for(Entry<String,Integer> entry : map.entrySet()){
max = Math.max(max,entry.getValue());
}
// 21. 최소 2번 이상 주문된 조합이며, 해당 횟수와 일치하는 조합은 ArrayList에 삽입.
for(Entry<String,Integer> entry : map.entrySet()){
if(max >=2 && entry.getValue() == max)
answer.add(entry.getKey());
}
}
// 22. 추가된 조합들을 오름차순 정렬.
Collections.sort(answer);
return answer;
}
}