[프로그래머스(Programmers)][자바(java)] (Lv2) 메뉴 리뉴얼

 

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

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

 

문제 풀이

 

import java.util.*;

public class Solution {
	
	int max;
	
	public void com( int k, int s, int n, int m, char d[], int a[], boolean v[], Map<String,Integer> hm ) {
		if( k == m ) {
			StringBuilder sb = new StringBuilder();
			for( i = 0; i < m; i++ )
				sb.append( d[a[i]] );
			String key = sb.toString();
			hm.put( key, hm.getOrDefault( key, 0 ) + 1 );
			max = Math.max( max, hm.get( key ) );
			return;
		}
		for( i = s; i < n; i++ ) {
			if( !v[i] ) {
				v[i] = true;
				a[k] = i;
				com( k + 1, i + 1, n, m, d, a, v, hm );
				v[i] = false;
			}
		}
	}
	
	public String[] solution(String[] orders, int[] course) {
        	Map<String,Integer> hm;
    		PriorityQueue<String> pq = new PriorityQueue<>();
        	int no = orders.length, nc = course.length, n, m, i, j;  char o[];
        	for( i = 0; i < nc; i++ ) {
        		hm = new HashMap<>();
        		max = 0;
        		for( j = 0; j < no; j++ ) {
        			o = orders[j].toCharArray();
        			Arrays.sort(o);
        			n = o.length; 
        			m = course[i];
        			if( n >= m )
        				com( 0, 0, n, m, o, new int[n], new boolean[n], hm );
        		}
        		if( max == 1 )
        			continue;
        		for( String s : hm.keySet() ) 
        			if( hm.get( s ) == max )
        				pq.add( s );
        	}
        	String menu[] = new String[pq.size()];  i = 0;
       		while( !pq.isEmpty() )
        		menu[i++] = pq.poll();
        	return menu;
    	}
}

 

*  완전 탐색, 해쉬, 최소힙

-  입력값의 범위를 보니 완전탐색을 해도 괜찮겠다고 판단이 됨
-  요리의 조합( String )을 key로 하고 그것이 주문된 인원 수( Integer )를 value로 하는 HashMap 생성
-  course[]를 순회하며 HashMap을 초기화 한 후 요리 course[i]개 코스의 모든 조합을 구하고 HashMap에 넣는다
 ( 이 때 가장 많이 주문된 개수를 구함 )
-  요리 n개 코스 당 가장 많이 주문된 조합들을 우선순위 큐( 최소힙; 메뉴 조합이 알파벳 순으로 먼저인 것이 먼저 나옴 )에 모두 넣고 리턴할 배열에 담는다