메뉴 리뉴얼

메뉴 리뉴얼

코딩테스트 연습 - 메뉴 리뉴얼 | 프로그래머스 (programmers.co.kr)

문제

n개의 메뉴로 구성된 코스 중 가장 많이 주문되는 코스를 등록한다.

ex) AB가 두 번 BC, CD가 세 번 주문되었다면 BC와 CD 모두 n개의 메뉴로 구성된 코스로 등록

위와 같은 방식으로 n개의 메뉴로 구성된 코스 목록을 배열에 담아 오름차순으로 정렬 후 리턴한다.

풀이

접근방식)

처음에는 orders에 쓰이는 모든 메뉴중에서 course[i]개 만큼 골라서 해당 코스가 몇 번 주문되는지 판별했는데 극닥적인 경우 26개의 메뉴중 2개를 고르는 경우의 수가 존재할 수 있기 때문에 각 주문메뉴에서 나올 수 있는 코스로 범위를 좁혔다.

알고리즘)

orders[i]의 메뉴들 중 course[j]개 만큼 조합하여 코스를 구성한다. 해당 코스가 orders에 몇 번 포함되는지 카운팅한다.(동시에 최댓값 Max를 구한다) 2번 이상 나오는 코스들의 메뉴목록과 count를 Map에 추가한다. Map을 count값을 기준으로 내림차순 정렬한다. count값이 Max값과 같은 메뉴목록들만 List에 추가한다. 1 ~ 5의 과정을 course.length만큼 반복한다. List의 값을 정렬한다.

코드

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; class Solution { String[] order; Map testMap; int o_num; int max = 0; char[] menu = new char[26]; boolean[] isused = new boolean[26]; char[] C = new char[26]; public void Combination(int cnt, int index,int c_num,String str){ if (cnt == c_num) // orders[i]로 만들 수 있는 c_num개 코스 { String course = ""; String[] c = new String[c_num]; int count = 0; boolean contain = true; for (int i = 0; i < c_num; i++){ c[i] = Character.toString(C[i]); course += Character.toString(C[i]); } for(int i = 0;i < order.length;i++) { contain = true; for(int j = 0 ; j < c_num ; j++){ if(!order[i].contains(c[j])) contain = false; } if(contain == true) // 주문한 단품메뉴 조합에 c_num개의 코스가 모두 포함되면 count++ count++; } if(max < count) // 가장높은 주문횟수 max = count; if(count > 1 && max == count){ //2번이상 주문 됐으면서 현재 최댓값과 같은 경우 //System.out.printf("course %s count %d

",course,count); testMap.put(course,count); } return; } for (int i = index; i < str.length(); i++) // 메뉴 구성 { C[cnt] = str.charAt(i); Combination(cnt + 1, i + 1,c_num,str); } } public ArrayList solution(String[] orders, int[] course) { String[] answer = {}; ArrayList courseList = new ArrayList(); order = orders.clone(); for(int i = 0 ;i < course.length;i++){ testMap = new HashMap(); max = 0; for(int j = 0; j < orders.length;j++){ char[] stringToChar = orders[j].toCharArray(); Arrays.sort(stringToChar); // XY, YX와 같은 중복제거 String sortedString = new String(stringToChar); Combination(0,0,course[i],sortedString); } List listKeySet = new ArrayList<>(testMap.keySet()); Collections.sort(listKeySet, (value1, value2) -> (testMap.get(value2).compareTo(testMap.get(value1)))); // 가장 많이 주문된 코스를 선택하기 위해 정렬 for(String key : listKeySet) { if(testMap.get(key) < max) // 정렬되어있으므로 이후의 값은 포함X break; courseList.add(key); //System.out.println("key : " + key + " , " + "value : " + testMap.get(key)); } } Collections.sort(courseList); // System.out.print(courseList); return courseList; } }

from http://sy4406.tistory.com/42 by ccl(A) rewrite - 2021-09-20 04:27:39