[프로그래머스/Level2] 메뉴 리뉴얼 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• DFS

1. 각 손님이 주문한 단품메뉴들을 오름차순으로 정렬한다.

(여기서 향상형 for문으로 orders 원소 값 받고 오름차순한 결과 저장하려다가 틀렸다....)

for(int i = 0 ; i < orders.length ; i++) {
    char[] ch = orders[i].toCharArray();
    Arrays.sort(ch);

    orders[i] = String.valueOf(ch); // 정렬 결과 저장
}

 

 

2. 각 주문을 기준으로 course 배열의 단품메뉴들의 갯수 길이(courseLen) 만큼의 조합을 만든다.

for (int courseLen : course) {
    for(String order : orders)
        comb(order, courseLen, "");     
}

 

private static void comb(String order, int cnt, String tmp) {
    if (cnt == 0) {
        map.put(tmp, map.getOrDefault(tmp, 0) + 1);
        return;
    }

    // 0부터 len까지의 조합
    for (int i = 0; i < order.length(); i++) {
        comb(order.substring(i + 1), cnt - 1, tmp + order.charAt(i));
    }
}

 

3. 가장 많이 주문된 횟수가 최소 2번 이상이고, 해당 조합이 주문된 횟수와 가장 많이 주문된 횟수가 일치한다면, 정답 리스트에 해당 조합을 추가한다.

if(!map.isEmpty()) {
    List<Integer> cntList = new ArrayList<>(map.values());
    int max = Collections.max(cntList); // 가장 많이 주문된 횟수

    if(max > 1) // 최소 2번 이상 주문된 조합
        for(String key : map.keySet())
            if(map.get(key) == max)
                result.add(key);

    map.clear();
}

 

 

4. 정답 리스트를 오름차순으로 정렬한 후, 배열로 변환한다.

Collections.sort(result);
return result.toArray(new String[0]);	// int형 리스트를 int형 배열로 변환

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static List<String> result = new ArrayList<>();
    static Map<String, Integer> map = new HashMap<>();
    
    public String[] solution(String[] orders, int[] course) {
        
        // 1. 각 주문 정렬
        for(int i = 0 ; i < orders.length ; i++) {
            char[] ch = orders[i].toCharArray();
            Arrays.sort(ch);
            
            orders[i] = String.valueOf(ch); // 🔔 정렬된 문자형 배열을 문자열로 변환해 저장
        }
        
        // 2. 각 주문을 기준으로 courseLen만큼의 조합 만들기
        for (int courseLen : course) {
            for(String order : orders)
                comb(order, courseLen, "");
            
            // 3. 가장 많은 조합을 answer에 저장
            if(!map.isEmpty()) {
                List<Integer> cntList = new ArrayList<>(map.values());
                int max = Collections.max(cntList); // 가장 많이 주문된 횟수
                
                if(max > 1) // 최소 2번 이상 주문된 조합
                    for(String key : map.keySet())
                        if(map.get(key) == max)
                            result.add(key);
                
                map.clear();
            }
        }
        
        Collections.sort(result);
        
        return result.toArray(new String[0]);
    }
    
    private static void comb(String order, int cnt, String tmp) {
        if (cnt == 0) {
            map.put(tmp, map.getOrDefault(tmp, 0) + 1);
            return;
        }
        
        // 0부터 len까지의 조합
        for (int i = 0; i < order.length(); i++) {
            comb(order.substring(i + 1), cnt - 1, tmp + order.charAt(i));
        }
    }
}
 

 

 

 

➕ 다른 풀이 방식

- 멋진 풀이...

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

 

 

- 멋진 풀이.. Map 관련 메소드를 까먹었다면 쓰기 좋은 풀이..

[알고리즘 문제풀이] 프로그래머스 - 메뉴 리뉴얼 / JAVA(자바)

---

💦 어려웠던 점

- 문제를 이해하는 데 15분 정도 걸린 듯하다

- 순서를 제대로 세우지 못했다! 담엔 꼭 순서를 먼저 적어두고 코드를 작성하자ㅠㅠ

- 자료구조 한참 고민하다가 결국은 틀렸다는 슬픈ㅇ ㅣ야기.

틀린 코드 확인하기

import java.util.*;
 
class Solution {
    static List<Character> candidates = new ArrayList<>();
    static boolean[] visited;
    static List<String> result = new ArrayList<>();
    
    public String[] solution(String[] orders, int[] course) {
        Map<Character, Integer> map = new HashMap<>();
        
        // 등장 횟수가 2번 이상인 요리 후보 생성
        for (String order : orders) {
            for (char c : order.toCharArray()) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
        }
        
        for (char key : map.keySet()) {
            if (map.get(key) >= 2) {
                candidates.add(key);
            }
        }
        
        Collections.sort(candidates);
        
        // 코스 조합 생성
        for (int c : course) {
            visited = new boolean[candidates.size()];
            dfs(0, 0, c, "");
        }
        
        Collections.sort(result);
        
        // 최소 2명 이상의 손님에게 주문된 코스 조합 선택
        List<String> realAns = new ArrayList<>();
        for (String cook : result) {
            int[] cntArr = new int[cook.length()];
            for (String order : orders) {
                for (int i = 0; i < cook.length(); i++) {
                    if (order.contains(cook.substring(i, i + 1))) {
                        cntArr[i]++;
                    }
                }
            }
            boolean b = true;
            for (int i = 0; i < cntArr.length; i++) {
                if (cntArr[i] < 2) {
                    b = false;
                    break;
                }
            }
            
            if (b) realAns.add(cook);
        }
        
        return realAns.toArray(new String[0]);
    }
    
    private static void dfs(int idx, int depth, int targetCnt, String str) {
        if (depth == targetCnt) {
            result.add(str);
            return;
        }
        
        for (int i = idx; i < candidates.size(); i++) {
                visited[i] = true;
                dfs(i + 1, depth + 1, targetCnt, str + candidates.get(i));
                visited[i] = false;
            }
        }
    }
}
 

 

 

 

🧐 새로 알게 된 내용

- HashMap의 value들을 리스트에 저장하고, 오름차순 정렬해 그 중 최댓값 가져오기

 List<Integer> cntList = new ArrayList<>(map.values());

 Collections.max(cntList);

 

- Integer형 리스트를 배열로 변환 (람다식 활용)

  result.toArray(new String[0]); 

 

① 조합 만들 땐 정렬을 고려하자

② HashMap의 기본 형태 = <Name, Cnt>

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[2021 카카오 코딩테스트] 메뉴 리뉴얼 - 자바 java

[프로그래머스,Level 2] 메뉴 리뉴얼 (JAVA 구현)

https://youtu.be/Jb34jY91450?feature=shared