[programers] 순위검색 (dfs & binary search)

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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

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

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

			dfs(arr.length - 1, "", 0, arr);
		}

		for (String key : map.keySet()) {
			List<Integer> score = map.get(key);
			Collections.sort(score);
		}

		for (int i = 0; i < query.length; i++) {
			query[i] = query[i].replaceAll(" and ", "");
			String[] arr = query[i].split(" ");
			int score = Integer.parseInt(arr[1]);

			answer[i] = search(arr[0], score);
		}
		return answer;
	}

	static void dfs(int lastIndex, String pos, int depth, String[] info) {
		if (depth >= lastIndex) {
			String score = info[lastIndex];

			if (!map.containsKey(pos)) {
				map.put(pos, new ArrayList<>());
			}
			map.get(pos).add(Integer.parseInt(score));
			return;
		}

		dfs(lastIndex, pos + "-", depth + 1, info);
		dfs(lastIndex, pos + info[depth], depth + 1, info);
	}

	static int search(String str, int score) {
		if (!map.containsKey(str)) {
			return 0;
		}

		List<Integer> scoreList = map.get(str);
		int start = 0, end = scoreList.size() - 1;
		while (start <= end) {
			int mid = (start + end) / 2;

			if (scoreList.get(mid) < score) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}

		return scoreList.size() - start;
	}
}

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

코딩테스트 연습 - 순위 검색

https://loosie.tistory.com/265

[프로그래머스] 2021 카카오 / 순위 검색 (Java)