[프로그래머스 2021 KAKAO BLIND RECRUITMENT ]메뉴 리뉴얼 -Java

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

코딩테스트 연습 - 메뉴 리뉴얼

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
class Solution {
		class Info{
			String order;
			int num;
			public Info(String order, int num) {
				this.order = order;
				this.num = num;
			}
		}
		public String[] solution(String []orders, int []course) {
			List<String> list = new ArrayList<>();
			
			for(int c=0; c<course.length; c++) {
				HashMap<String ,Integer> hm = new HashMap<>(); //입력 한 줄에 대해 
				int courseNum=course[c]; //코스요리 개수
				StringBuilder sb= new StringBuilder();
				
				for(int o=0; o<orders.length; o++) { //입력들어온 한줄의 길이!
					String order=orderSort(orders[o]);
					
					combi(0,0,order.length(),hm,order,sb,courseNum); //start
					
				}
				answerSelect(hm,list);
			}
			String [] answer= new String[list.size()];
			for(int i=0; i<list.size(); i++) answer[i]=list.get(i);
			Arrays.sort(answer);
			return answer;
		}


		private void combi(int cnt,int start, int length, HashMap<String, Integer> hm, String order, StringBuilder sb, int courseNum) {
			if(sb.length()==courseNum) { //다 뽑았으면
				String courseFood=sb.toString();
				//System.out.println(courseFood);
				if(hm.containsKey(courseFood)) hm.put(courseFood, hm.get(courseFood)+1);
				else hm.put(courseFood, 1);
				sb=new StringBuilder();
				return;
			}
			
			if(cnt==length) { //다 돌았는데 글자 못채우면 
				sb=new StringBuilder();
				return;
			}
			
			for(int i=start; i<length; i++) {
				sb.append(order.charAt(i));
				combi(cnt+1,i+1,length,hm,order,sb,courseNum); 
				sb.deleteCharAt(sb.length()-1);
			}
			
		}

		private void answerSelect(HashMap<String, Integer> hm, List<String> list) {
			List<Info> orderList=new ArrayList<>();
			for(String order : hm.keySet()) orderList.add(new Info(order, hm.get(order)));
			Collections.sort(orderList, (o1,o2)->(o2.num-o1.num));
			if(orderList.size()==0 ) return;
			int num=orderList.get(0).num;
			if(num<2) return;
			
			for(int i=0; i<orderList.size(); i++) {
				Info info = orderList.get(i);
				if(info.num==num) list.add(info.order);
				else break;
			}
			return;
		}

		private String orderSort(String order) {
			PriorityQueue<Character> pq = new PriorityQueue<>();
			StringBuilder sb= new StringBuilder();
			
			for(int i=0; i<order.length(); i++) pq.offer(order.charAt(i));
			while(!pq.isEmpty()) {
				sb.append(pq.poll());
			}
			return sb.toString();
		}
	}

소요시간 : 1시간 20분

 

 

로직을 살펴보면

 

1.orders배열에서 한 개를 빼서 소문자로 바꿔줍니다.

(출력 배열 안의 알파벳을 오름차순으로 정렬해야하기 때문에 미리 해줍니다)

2.dfs를 통해 course의 길이만큼 음식을 뽑아줍니다.

3.HashMap을 이용해 각 음식이 몇 번 뽑혔는지 체크해줍니다.

4.HashMap을 List로 바꿔서 2명 이상의 손님에게 뽑힌 코스요리 중 가장 많이 뽑힌 코스요리를 answerList에 넣어줍니다.

 

처음에 2번을 짤 때 문제를 똑바로 안 읽고 for문으로 돌리다가 다시 dfs로 바꿨습니다...ㅎ

 

시간은 좀 오래 걸렸지만 그렇게 어려운 문제라고는 생각되지 않습니다!