[programmers] 순위 검색

import java.util.*;

class Solution {
	static Map<ArrayList<String>, ArrayList<Integer>> map;

	public int[] solution(String[] info, String[] query) {
		int[] answer = new int[query.length];

		map = new HashMap<>();
		String[][] row = new String[info.length][5];

		for (int i = 0; i < info.length; i++) {
			row[i] = info[i].split(" ");
		}

		Arrays.sort(row, new Comparator<String[]>() {

			@Override
			public int compare(String[] o1, String[] o2) {
				return Integer.parseInt(o1[4]) - Integer.parseInt(o2[4]);
			}
		});

		for (int i = 0; i < info.length; i++) {
			boolean[] used = new boolean[5];
			comb(row[i], used, 0);
		}

		ArrayList<String> tmp = new ArrayList<>();

		for (int i = 0; i < query.length; i++) {
			String[] q = query[i].split(" ");

			for (int j = 0; j < q.length; j += 2) {
				tmp.add(q[j]);
			}

			int num = Integer.parseInt(q[7]);

			ArrayList<Integer> result = map.get(tmp);

			if (result != null) {
				int st = 0, end = result.size() - 1;

				while (st <= end) {
					int mid = (st + end) / 2;

					if (result.get(mid) < num) {
						st = mid + 1;
					} else {
						end = mid - 1;
					}
				}

				answer[i] = result.size() - st;
			}

			tmp.clear();
		}

		return answer;
	}

	static void comb(String[] row, boolean[] used, int index) {
		ArrayList<String> list = new ArrayList<>();

		for (int i = 0; i < used.length - 1; i++) {
			if (used[i]) {
				list.add(row[i]);
			} else {
				list.add("-");
			}
		}

		map.computeIfAbsent(list, key -> new ArrayList<>()).add(Integer.parseInt(row[4]));

		if (index == used.length)
			return;

		for (int i = index; i < used.length - 1; i++) {
			if (!used[i]) {
				used[i] = true;
				comb(row, used, i + 1);
				used[i] = false;
			}
		}
	}
}