Menu

Subscribe

[JAVA/프로그래머스] 2021 KAKAO BLIND RECRUITMENT: 메뉴 리뉴얼

HEESOO on Programmers

👀 문제

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

👊 도전

1. 설계

  1. orders[i]의 조합을 구한다. 이때 조합의 길이는 course 값을 이용한다.
  2. 구한 조합은 combMap에 저장한다. 조합한 메뉴 길이가 가장 긴 것을 리턴해야하므로(같은 값이 있으면 여러 개 리턴) sizeMap에 메뉴 길이의 발생 횟수의 최댓값을 저장한다.
  3. combMap, sizeMap이 완료하면, entrySet()로 순회하며, 조합 i의 개수가 2 이상이고, 조합들 중 i 문자열 길이와 같은 것 중 최댓값 개수인 것만 result에 저장한다.
  4. 배열 형태로 리턴해야하므로 result(ArrayList)를 Array로 변환해서 리턴한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
import java.util.*;

class Solution {
    Map<String, Integer> combMap;
    Map<Integer, Integer> sizeMap;
    
    public String[] solution(String[] orders, int[] course) {
        String[] answer = {};
        combMap=new HashMap<>();
        sizeMap=new HashMap<>();
        
        for(String order:orders){
            char[] array=order.toCharArray();
            Arrays.sort(array);
            for(int c:course){
                comb(0, new StringBuilder(), array, c);
            }
        }
        
        List<String> result=new ArrayList<>();
        for(Map.Entry<String, Integer> entry:combMap.entrySet()){
            if(entry.getValue()>1 && entry.getValue()==sizeMap.get(entry.getKey().length())){
                result.add(entry.getKey());
            }
        }
        
        Collections.sort(result);
        answer=result.toArray(new String[result.size()]);
        return answer;
    }
    
    public void comb(int idx, StringBuilder sb, char[] array, int depth){
        if(sb.length()==depth){
            combMap.put(sb.toString(), combMap.getOrDefault(sb.toString(), 0)+1);
            sizeMap.put(sb.length(), Math.max(sizeMap.getOrDefault(sb.length(), 0), combMap.get(sb.toString())));
            return;
        }
        
        for(int i=idx;i<array.length;i++){
            comb(i+1, sb.append(array[i]), array, depth);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 조합을 구한다
    • comb()
    • idx: array 순회 인덱스. array[idx]를 선택할지 말지 체크한다.
    • sb: 조합 생성하는 StringBuilder. 문자열 삽입이 빈번히 일어나므로 String보다 StringBuilder를 사용하는 것이 낫다.
    • array: 조합할 문자 배열 대상
    • depth: 만들 조합의 길이
    • “XY”, “YX”는 같은 것으로 생각하므로, solution()에서 comb()를 호출하기 전 Arrays.sort()로 조합할 char 배열을 오름차순 정렬한다.
    • 조합 생성이 완료되면 combMap에 sb를 넣는다. value는 조합을 통해 생성된 sb의 횟수이다.
    • sizeMap에 sb.length()의 max를 저장한다. 조합 문자열의 길이가 같은 것 중 max만 리턴할 수 있으므로, 이를 체크하기 위해 사용할 것이다.
    • 재귀로 조합을 찾는다. 이때 array[i]를 선택하거나 하지 않는 경우를 생각한다. 선택한 경우로 재귀를 돌고 오면, sb에는 array[i]가 아직 들어가있으므로 deleteCharAt()으로 array[i]를 삭제해야 한다.
  2. 조합 중 조건에 맞는 값을 리턴한다
    • 조합 횟수가 2 이상이고 길이가 최댓값인 것만 result에 넣는다.
    • 오름차순으로 정렬하여 리턴한다.

👏 해결 완료!