<div id="readability-page-1" class="page"><div><h2 id="문제-설명">문제 설명</h2>
<a href="https://school.programmers.co.kr/learn/courses/30/lessons/72411">https://school.programmers.co.kr/learn/courses/30/lessons/72411</a>
<h2 id="풀이">풀이</h2>
<ol>
<li>
ABCFG 혹은 AC와 같은 주문 배열로부터 길이가 2, 3, 4인 조합 문자열을 뽑아냅니다. 
ex) AB, AC, AF, AG ...
</li>
<li>
1.에서 뽑아낸 각 문자열에 대해 주문횟수를 저장한 맵을 만듭니다.
</li>
</ol>
<pre><code>{ "AB": 1, "AC": 2, "AF": 3 ... }</code></pre>
<ol start="3">
<li>2.에서 뽑아낸 문자열 중 가장 큰 값을 가진 문자열을 모두 선택한 뒤 정렬하여 돌려줍니다.</li>
</ol>
대략적인 구현은 위와 같고, 가장 문제가 될만한 부분은 1.에서 조합 문자열을 뽑아내는 부분일것 같습니다.
가능한 모든 문자열 조합을 찾아내는 코드는 일반적인 DFS 알고리즘을 통해 구현할 수 있습니다.
<pre><code>public void main(String[] args) {
	List&lt;String&gt; result = new ArrayList&lt;&gt;();
 
 // abcde의 다섯 글자 중에서 길이가 2인 문자열을 뽑아낸다.
	findCombinations("abcde", 2, new StringBuilder(), 0, result);
}

private void findCombinations(String alphabet, int length,
 StringBuilder current, int index, List&lt;String&gt; result) {
 
 if (current.length() == length) {
 result.add(current.toString());
 return;
 }

 for (int i = index; i &lt; alphabet.length(); i++) {
 current.append(alphabet.charAt(i));
 findCombinations(alphabet, length, current, i + 1, result);
 current.deleteCharAt(current.length() - 1);
 }
}</code></pre>
이제 전체 코드를 살펴보겠습니다.
<pre><code>public String[] solution(String[] orders, int[] course) {
 List&lt;String&gt; answer = new ArrayList&lt;&gt;();

 for (int numMenus : course) {
 List&lt;String&gt; combinations = new ArrayList&lt;&gt;();
 for (String order : orders) {
 findCombinations(
 order, numMenus, new StringBuilder(), 0, combinations);
 }

 Map&lt;String, Integer&gt; numOrdersByMenu =
 getNumOrdersByMenu(orders, combinations);

 // 최소 2명 이상이 주문한 메뉴만 코스 요리에 포함
 int maxNumOrders = 2;
 for (String key : numOrdersByMenu.keySet()) {
 int numOrder = numOrdersByMenu.get(key);
 if (numOrder &gt;= maxNumOrders) {
 maxNumOrders = numOrder;
 }
 }

 for (String key : numOrdersByMenu.keySet()) {
 if (numOrdersByMenu.get(key) == maxNumOrders) {
 answer.add(key);
 }
 }
 }

 String[] ret = new String[answer.size()];
 for (int i = 0; i &lt; answer.size(); i++) {
 ret[i] = answer.get(i);
 }

 Arrays.sort(ret);
 return ret;
}

private static Map&lt;String, Integer&gt; getNumOrdersByMenu(
 String[] orders, List&lt;String&gt; combinations) {
 Map&lt;String, Integer&gt; map = new HashMap&lt;&gt;();
 for (String combination : combinations) {
 for (String order : orders) {
 int numIncluded = 0;
 for (int i = 0; i &lt; combination.length(); i++) {
 if (order.contains("" + combination.charAt(i))) {
 numIncluded++;
 }
 }

 if (numIncluded == combination.length()) {
 map.put(combination, map.getOrDefault(combination, 0) + 1);
 }
 }
 }
 return map;
}

private void findCombinations(String alphabet, int length,
 StringBuilder current, int index, List&lt;String&gt; result) {
 if (current.length() == length) {
 // XY, YX 같은 중복 케이스를 제거하기 위해 정렬 후 집어넣음
 String str = current.toString();
 char[] charArray = str.toCharArray();
 Arrays.sort(charArray);

 result.add(String.valueOf(charArray));
 return;
 }

 for (int i = index; i &lt; alphabet.length(); i++) {
 current.append(alphabet.charAt(i));
 findCombinations(alphabet, length, current, i + 1, result);
 current.deleteCharAt(current.length() - 1);
 }
}</code></pre></div></div>

leejh3224.log

문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/72411
풀이
ABCFG 혹은 AC와 같은 주문 배열로부터 길이가 2, 3, 4인 조합 문자열을 뽑아냅니다.
ex) AB, AC, AF, AG ...
1.에서 뽑아낸 각 문자열에 대해 주문횟수를 저장한 맵을 만듭니다.
{ "AB": 1, "AC": 2, "AF": 3 ... }
2.에서 뽑아낸 문자열 중 가장 큰 값을 가진 문자열을 모두 선택한 뒤 정렬하여 돌려줍니다.
대략적인 구현은 위와 같고, 가장 문제가 될만한 부분은 1.에서 조합 문자열을 뽑아내는 부분일것 같습니다.
가능한 모든 문자열 조합을 찾아내는 코드는 일반적인 DFS 알고리즘을 통해 구현할 수 있습니다.
public void main(String[] args) {
 List<String> result = new ArrayList<>();
 // abcde의 다섯 글자 중에서 길이가 2인 문자열을 뽑아낸다.
 findCombinations("abcde", 2, new StringBuilder(), 0, result);
}
private void findCombinations(String alphabet, int length,
 StringBuilder current, int index, List<String> result) {
 if (current.length() == length) {
 result.add(current.toString());
 return;
 }
 for (int i = index; i < alphabet.length(); i++) {
 current.append(alphabet.charAt(i));
 findCombinations(alphabet, length, current, i + 1, result);
 current.deleteCharAt(current.length() - 1);
 }
}
이제 전체 코드를 살펴보겠습니다.
public String[] solution(String[] orders, int[] course) {
 List<String> answer = new ArrayList<>();
 for (int numMenus : course) {
 List<String> combinations = new ArrayList<>();
 for (String order : orders) {
 findCombinations(
 order, numMenus, new StringBuilder(), 0, combinations);
 }
 Map<String, Integer> numOrdersByMenu =
 getNumOrdersByMenu(orders, combinations);
 // 최소 2명 이상이 주문한 메뉴만 코스 요리에 포함
 int maxNumOrders = 2;
 for (String key : numOrdersByMenu.keySet()) {
 int numOrder = numOrdersByMenu.get(key);
 if (numOrder >= maxNumOrders) {
 maxNumOrders = numOrder;
 }
 }
 for (String key : numOrdersByMenu.keySet()) {
 if (numOrdersByMenu.get(key) == maxNumOrders) {
 answer.add(key);
 }
 }
 }
 String[] ret = new String[answer.size()];
 for (int i = 0; i < answer.size(); i++) {
 ret[i] = answer.get(i);
 }
 Arrays.sort(ret);
 return ret;
}
private static Map<String, Integer> getNumOrdersByMenu(
 String[] orders, List<String> combinations) {
 Map<String, Integer> map = new HashMap<>();
 for (String combination : combinations) {
 for (String order : orders) {
 int numIncluded = 0;
 for (int i = 0; i < combination.length(); i++) {
 if (order.contains("" + combination.charAt(i))) {
 numIncluded++;
 }
 }
 if (numIncluded == combination.length()) {
 map.put(combination, map.getOrDefault(combination, 0) + 1);
 }
 }
 }
 return map;
}
private void findCombinations(String alphabet, int length,
 StringBuilder current, int index, List<String> result) {
 if (current.length() == length) {
 // XY, YX 같은 중복 케이스를 제거하기 위해 정렬 후 집어넣음
 String str = current.toString();
 char[] charArray = str.toCharArray();
 Arrays.sort(charArray);
 result.add(String.valueOf(charArray));
 return;
 }
 for (int i = index; i < alphabet.length(); i++) {
 current.append(alphabet.charAt(i));
 findCombinations(alphabet, length, current, i + 1, result);
 current.deleteCharAt(current.length() - 1);
 }
}

[2021 KAKAO BLIND RECRUITMENT] 메뉴 리뉴얼

댓글