문제에서 배열의 길이가 너무 길다면 이진탐색을 생각해보자.
근데 이게 레벨2라고?
split()
으로 지원자의 정보를 쪼갠다.map
에 정보들을 key로, 점수를 리스트인 value에 넣어준다.map
에 저장하는 것이다. map
의 value들을 정렬한다.answer
의 현재 인덱스에 넣어주고, 일치하는 지원자가 없으면 0을 넣어준다.import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
class Solution {
HashMap<String, List<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[] infos = info[i].split(" ");
dfs(infos, "", 0);
}
for (String key : map.keySet()) {
Collections.sort(map.get(key));
}
for (int i = 0; i < query.length; i++) {
String fixedQuery = query[i].replaceAll(" and ", "");
String[] questions = fixedQuery.split(" ");
if (map.containsKey(questions[0])) {
answer[i] = binarySearch(questions[0], Integer.parseInt(questions[1]));
} else {
answer[i] = 0;
}
}
return answer;
}
public void dfs(String[] infos, String key, int depth) {
if (depth == 4) {
if (!map.containsKey(key)) {
List<Integer> value = new ArrayList<>();
map.put(key, value);
}
map.get(key).add(Integer.parseInt(infos[4]));
return;
}
dfs(infos, key + "-", depth + 1);
dfs(infos, key + infos[depth], depth + 1);
}
public int binarySearch(String key, int score) {
List<Integer> scores = map.get(key);
int left = 0;
int right = scores.size() - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(scores.get(mid) < score) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return scores.size() - left;
}
}