프로그래머스 메뉴 리뉴얼(lvl2) 풀어보기

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42890

프로그래머스

 

---

문제 핵심

• 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.손님 번호주문한 단품메뉴 조합

  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번 주문됐습니다.

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

---

문제 풀이법

-만드려는 조합개수별로

만들수있는 조합모두만들기

그중 가장 인기있는 조합 리턴하기

---

코드

  public static String[] solution(String[] orders, int[] course) {

        String[] answer = {};

        Map<Integer, Map<String, Integer>> map2 = new LinkedHashMap<>();

        for (int c : course) {

            Map<String, Integer> map = new LinkedHashMap<>();

            map2.put(c, map);

        }

        for (String order : orders) {

            char[] orArr = order.toCharArray();

            Arrays.sort(orArr);

            for (int i = 0; i < orArr.length; i++) {

                char c = orArr[i];

                dfs(orArr, c + "", i + 1, i + "", map2);

            }

        }

        System.out.println(map2);

        List<String>bests=new ArrayList<>();

        for (Map.Entry<Integer, Map<String, Integer>> entry : map2.entrySet()) {

            Map<String, Integer> value = entry.getValue();

            int max = 2;

            List<String>best=new ArrayList<>();

            System.out.println(entry.getKey()+"조합 메뉴시작");

            for (Map.Entry<String, Integer> inner : value.entrySet()) {

                String menu = inner.getKey();

                Integer count = inner.getValue();

                if (max ==count) {

                    best.add(menu);

                    max=count;

                }

                else if (max <count) {

                    best.clear();

                    best.add(menu);

                    max=count;

                }

            }

            System.out.println(best);

            for(String b:best){

                bests.add(b);

            }

        }

        Collections.sort(bests);

        answer = bests.toArray(new String[0]);

        System.out.println(Arrays.toString(answer));

        return answer;

    }

    public static void dfs(char[] orArr, String sout, int start, String key,

            Map<Integer, Map<String, Integer>> map2) {

        for (int ii = start; ii < orArr.length; ii++) {

            String menu = sout + orArr[ii];

            int len = menu.length();

            System.out.println(sout + orArr[ii] + "," + key + ii+","+len+","+map2.containsKey(len));

            if (map2.containsKey(len)) {

                Map<String, Integer> map = map2.get(len);

                int count = 1;

                if (map.containsKey(menu)) {

                    count = map.get(menu) + 1;

                }

                map.put(menu, count);

                map2.put(len, map);

            }

            // System.out.println("자식 시작: " + ii);

            dfs(orArr, menu, ii + 1, key + ii, map2);

            // System.out.println("백트래킹: " + ii + Arrays.toString(visited));

        }

    }

 

---

결과

---

gpt피드백

-알고리즘적으로 개선할 건 크게 2개야.

첫째 지금은 각 주문에서 모든 길이의 조합을 전부 생성해.

A
AB
ABC
ABCD
ABCDE
...

 

그런데 course = [2, 3, 4]라면 사실 1개짜리나 5개 이상 조합은 필요가 없어.

---

배운점느낀점

-아씨 

["XYZ", "XWY", "WXA"]

[2,3,4]

이케이스 에서 막혔었다

XW=1WX=1 같은 조합이 이렇게 다르게 됐었다

map키는 다른걸로 당연히 인식한다

곰곰히 고민하다 결국 gpt한테 물어보고 힌트를 받았다

아깝다 직전 문제랑 너무 비슷해서 혼자 풀 수 있었는데