231005 순위 검색

private Map<String, List<Integer>> map = new HashMap<>();

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

	for (String inf : info) {
		String[] infoParts = inf.split(" ");
		int score = Integer.parseInt(infoParts[4]);
		generateCombinations(infoParts, 0, "", score);
	}

	for (List<Integer> list : map.values()) {
		Collections.sort(list);
	}

	for (int i = 0; i < query.length; i++) {
		String[] queryParts = query[i].replace(" and ", "").split(" ");
		int score = Integer.parseInt(queryParts[1]);
		answer[i] = binarySearch(queryParts[0], score);
	}

	return answer;
}

private void generateCombinations(String[] infoParts, int depth, String prefix, int score) {
	if (depth == 4) {
		map.computeIfAbsent(prefix, k -> new ArrayList<>()).add(score);
		return;
	}

	generateCombinations(infoParts, depth + 1, prefix + infoParts[depth], score);
	generateCombinations(infoParts, depth + 1, prefix + "-", score);
}

private int binarySearch(String key, int score) {
	if (map.containsKey(key)) {
		List<Integer> list = map.get(key);
		int left = 0;
		int right = list.size() - 1;

		if (list.get(right) < score) {
			return 0;
		}

		while (left < right) {
			int mid = (left + right) / 2;

			if (list.get(mid) < score) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		return list.size() - left;
	}

	return 0;
}

출처:https://school.programmers.co.kr/learn/courses/30/lessons/72412