2021 KAKAO BLIND 코딩테스트 메뉴 리뉴얼 풀이 Java

 

 

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

프로그래머스

 

포인트 : 조합 사용, 정렬

import java.util.*;

public class Menu {
	public static void main(String[] args) {
		Solution sol = new Solution();

		String[] orders = { "ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH" };
		int[] course = { 2, 3, 4 };

		String[] ans = sol.solution(orders, course);

		for (String a : ans)
			System.out.println(a);
	}
}

class Solution {
	Map<String, Integer> map = new HashMap<String, Integer>();

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

		List<String> list = new ArrayList<>();
		String[] answer = {};

		for (int c : course) {
			map = new HashMap<String, Integer>();

			for (String order : orders) {

				if (order.length() < c)
					continue;

				char[] o = order.toCharArray();
				Arrays.sort(o);

				combination(o, new boolean[o.length], 0, c);
			}

			if (map.size() == 0)
				continue;

			int max = Collections.max(map.values());

			if (max >= 2) {
				for (Map.Entry<String, Integer> entry : map.entrySet()) {
					String k = entry.getKey();
					int v = entry.getValue();

					if (v == max)
						list.add(k);
				}
			}
		}

		answer = list.toArray(new String[0]);
		Arrays.sort(answer);

		return answer;
	}

	public void combination(char[] comb, boolean[] visited, int idx, int r) {
		if (r == 0) {
			String s = "";

			for (int i = 0; i < comb.length; i++)
				s = visited[i] == true ? s += comb[i] : s;

			map.put(s, map.getOrDefault(s, 0) + 1);

			return;
		}

		if (idx == comb.length) {
			return;
		}

		visited[idx] = true;
		combination(comb, visited, idx + 1, r - 1);
		visited[idx] = false;
		combination(comb, visited, idx + 1, r);

	}
}