[JAVA] 프로그래머스 - 메뉴 리뉴얼

문제내용

https://programmers.co.kr/learn/courses/30/lessons/72411

코딩테스트 연습 - 메뉴 리뉴얼

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

손님 번호주문한 단품메뉴 조합

1번 손님	A, B, C, F, G
2번 손님	A, C
3번 손님	C, D, E
4번 손님	A, C, D, E
5번 손님	B, C, F, G
6번 손님	A, C, D, E, H

가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

코스 종류메뉴 구성설명

요리 2개 코스	A, C	1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스	C, D, E	3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스	B, C, F, G	1번, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스	A, C, D, E	4번, 6번 손님으로부터 총 2번 주문됐습니다.

---

[문제]

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

• orders 배열의 크기는 2 이상 20 이하입니다.
• orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
  • 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
  • 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
•  배열의 크기는 1 이상 10 이하입니다.
  • course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
  • course 배열에는 같은 값이 중복해서 들어있지 않습니다.
• 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
  • 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
  • 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
  • orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.

---

문제 접근 방법

처음 문제를 접하고 문제 이해가 잘 안돼서 머릿속으로 5분 정도 생각한것 같다. 국어능력이 딸리는건지(나만그래..?);;;

그래도 풀어내서 기분은 좋음 ㅎㅎㅎ

여튼 문제 설명을 예제1번으로 간략하게 해보자면..

 

먼저

String[] orders = {"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"};

int[] course = {2,3,4};

이렇게 배열 두개가 주어질때 하나씩 의미를 알아보자.

1. 배열 orders의 요소 하나당 단품메뉴를 조합해 주문한 사람을 의미한다. 즉, orders[0]은 첫번째 손님이 단품메뉴 "A, B, C, F, G" 를 주문했다는 의미이다.
2. 배열 course는 코스요리에 나오는 단품메뉴 조합을 의미한다. 즉, orders[0]일때의 손님(첫번째 손님)만 따진다면
   course 가 2일때 = (AB, AC, AF, AG)
   course 가 3일때 = (ABC, ABF, ABG, ACF, ACG, AFG, BCF, BCG, BFG, CFG)
   course 가 4일때도 위와 마찬가지의 규칙으로 단품메뉴 4가지로 조합된 문자열이 나와야한다.
   참고로 course가 2일때 (AB)는 되는데 (BA)는 안되나 라고 생각하면 안되는게 맞다. 식탁에 올라온 음식이 A 올라오고 B가 올라오는거나 B가 올라오고 A가 올라는거나 똑같기 때문에 하나로 봐야한다.
3. 이제는 각 course마다 return값이 왜 "AC", "ACDE", "BCFG", "CDE" 이렇게 나오는지 알면 된다. AC만 예를 들면
   course가 2일때  = 1번째, 2번째, 4번째, 6번째 손님들이 AC로 구성되니 단품메뉴를 시켰다. 그리고 단품메뉴 2개로 조합된 메뉴중 AC의 조합이 가장 많이 주문됐기 때문에 course가 2일때 return 값이 AC가 나오는 것이다.
   나머지 course의 경우도 모두 마찬가지의 규칙을 따른다.

 

문제를 이해했다면 이제 풀이방법을 생각해보자.

1. 가장 먼저 각 손님들이 시킨 단품메뉴의 조합을 생각해야한다.
   이유는 단품메뉴의 조합을 통해 그 조합이 orders 손님들 중 얼마나 많이 주문 됐나 알아보기 위해서이다.
   각 손님마다 주문한 단품메뉴들의 조합이 어떻게 구성되는지 경우의 수를 구하기 위해서 백트래킹을 이용할 것이다.
   
   
2. 그럼 그 단품메뉴들의 조합이 몇번 주문됐는지 알기 위해선 어떻게 해야할까
   위의 1번을 통해 어떤 조합들이 나왔는지 구했다면 그 조합들을 저장해 놓을 공간이 필요하다.
   예를들어 우리는 가장먼저 첫번째 손님의 주문 "ABCFG" 으로 course가 2,3,4 일때 모든 조합들을 백트래킹을 통해 구할것이다. 그리고 첫번째 손님 조합을 다봤다면 두번째 손님의 주문 "AC"의 조합을 마찬가지로 구할것이다. 이때 첫번째 손님의 조합중 "AC"가 있고 두번째 손님의 조합중 "AC"가 있다. 그렇다면 지금까지 "AC" 조합이 두번 나왔다는것을 알기위해 첫번째 손님일때 조합들을 특정 저장공간에 저장해놓고 두번째 손님의 조합과 비교할 필요가 있다. 즉, n번째 손님일땐 1번째~n-1번째 손님의 모든 조합과 비교할 필요가 있기 때문에 특정 저장공간을 필요로한다.
   
   
3. 2번까지 이해하고 알겠는데... 그럼 어떤 저장 공간을 사용 해야하는지 생각해보자.
   가장 많이 쓰이는 배열을 사용하려면.. course의 각 요소크기의 배열들을 여러개 생성해야한다. 그리고 course는 주어지는 입력값으로 요소의 개수는 1~10까지 변할 수 있다. 그러므로 배열은 부적합하다.
   course의 요소 개수가 여러개가 될수 있기때문에 Stack, queue, ArrayList, List 모두 마찬 가지로 부적합하다.
   하지만 HashMap의 경우는 어떨지 생각해보자.
   
   HashMap을 사용한다면 Key와 Value에 어떤 값을 넣어야 할까.
   단품메뉴들의 조합은 유일한 것이기 때문에 Key에 어울린다. 그리고 HashMap의 특징을 이용해
   단품메뉴들의 조합을 Key라고 했을때 Key가 중복됨에 따라 해당 Value가 증가한다면 우리는 해당 조합이 몇번 주문됐는지 알수 있다.
   
   즉,  HashMap<String, Integer> 를 선언해서 Key=조합된 단품메뉴, Value=조합된 단품메뉴 카운팅 이라고 정리할 수 있다.
   
   
   
4. 이젠 HashMap에 저장된 Key와 Value를 이용해 각 course의 경우마다 가장 많이 주문된 조합을 찾으면 된다.
   
   이게 뭔 말이냐면 현재 HashMap의 Key에는 조합된 단품메뉴가 저장돼있다. 그렇기 때문에
   coures가 2라면 Key의 길이가 2인 조합메뉴를 의미하게 된다.
   
   그리고 Value에는 조합된 메뉴들이 몇번 주문됐는지 저장돼있다. 그렇기 때문에 우리는
   Key의 길이가 2일때 Vaule의 최댓값을 알아내서 course가 2일 경우 손님들이 가장많이 주문한 조합된 단품메뉴들을 뽑아낼 수 있게 되는것이다.

 

위의 풀이를 간단하게 정리하면

조합하고 -> 카운팅하고 -> 각 course 마다 최대로 카운팅된 조합메뉴 선정 -> answer에 추가 -> answer 정렬 -> 답.

이런과정을 거치게된다.

 

풀이를 보고 생각해보자.

 

---

풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;

public class Solution {
	static HashMap<String, Integer> map = new HashMap<String, Integer>();
	
	public static ArrayList<String> solution(String[] orders, int[] course) {
		ArrayList<String> answer = new ArrayList<String>();
		StringBuilder sb= new StringBuilder();//각 단품메뉴를 조합할 변수
		
		//손님 한명씩 조합메뉴들을 살펴본다.
		for(int i=0; i<orders.length; i++) {
			char[] temp = orders[i].toCharArray();
			//정렬해주는 이유는 반환값의 요소들 또한 오름차순 정렬이기 때문
			Arrays.sort(temp);
			//i번째 손님일때 그 손님의 주문에서 각 코스마다 조합들을 찾기.
			for(int j=0; j<course.length; j++) {
				//백트래킹
				//com(i번째 손님 주문메뉴, 각 코스의 경우, 조합을 위한 인덱스, 단품메뉴를 조합할 변수, 종료조건을 알려줄 변수)
				com(temp,course[j],0,sb,0);
			}
		}
		
		for(int i=0; i<course.length; i++) {
			int max = Integer.MIN_VALUE;
			String key = "";//조합메뉴
			Integer value = null;//조합메뉴 카운팅된 횟수
			//최소 2번이상 주문된 메뉴들중 현재 코스의 길이와 같은 조합메뉴의 최대값을 찾음.
			for(Entry<String, Integer> ent:map.entrySet()) {
				key = ent.getKey();
				value = ent.getValue();
				if(value>=2 && key.length()==course[i]) {
					max = Math.max(max, value);
				}
			}
			
			//찾은 최댓값에 해당하면서 현재 코스의 길이에 맞는 조합메뉴를 추가
			for(Entry<String, Integer> ent:map.entrySet()) {
				key = ent.getKey();
				value = ent.getValue();
				if(value==max && key.length()==course[i]) {
					answer.add(key);
				}
			}
		}
		
		//정렬
		Collections.sort(answer);
		return answer;
	}
	
	//백트래킹
	public static void com(char[] temp, int course, int idx, StringBuilder sb, int depth) {
		//현재 코스의 길이로된 sb가 입력됐을때 종료
		//depth 대신 sb.length 가능.
		if(depth == course) {
			if(map.containsKey(sb.toString())){//이미 있는 메뉴면 카운팅 +1
				map.put(sb.toString(), map.get(sb.toString())+1);
			}else {//아니면 메뉴 추가
				map.put(sb.toString(), 1);
			}
			return;
		}
		
		//모든 조합 찾기.
		//for문에서 i번째 문자를 선택했을때 다음 재귀때는 i+1 즉, idx번째 문자를
		//선택하여 조합이 겹치지 않도록 설정.
		for(int i=idx; i<temp.length; i++) {
			sb.append(temp[i]);//sb에 선택문자 붙이기
			com(temp,course,i+1,sb,depth+1);//재귀
			//재귀 끝나면 sb값 원래대로 되돌려 놓기.
			sb.delete(sb.length()-1, sb.length());
		}
	}
}

---

마치며

이번 문제를 풀며 느낀건... 카카오 LV2문제인데 첫인상이 체감상 LV2같지 않은 문제였다. 한마디로 어려웠다 ㅠ

그래도 이번 문제덕에 해시맵도 오랜만에 써볼 수 있었고, 모든 경우의수의 조합을 따질때 i를 재정의해 겹치지 않도록 해볼 수 있어서 좋은 문제였다고 생각한다.