728x90
🔍 아이디어
✅ 지원자들의 스펙을 가능한 모든 경우의 수를 구해 _!Map!_ 의 _!key!_ 로 저장한다.
✅ 저장한 곳의 _!value!_ 에는 지원자의 점수를 저장해두고, 모든 순회가 종료되면 오름차순으로 정렬한다.
✅ _!query!_ 를 저장해둔 _!key!_ 의 형태로 변환하고 저장된 값이 있는지 찾는다.
✅ 값이 있다면, _!query!_ 의 코딩 기준 점수보다 높은 사람이 몇 명이 있는지 구하고, _!answer!_ 변수에 담아 반환한다.
import java.util.*;
class Solution {
Map<String, List<Integer>> map = new HashMap<>();
public int[] solution(String[] info, String[] query) {
int[] answer = new int[query.length];
for (String info_str : info) {
// 지원자의 스펙, 변화 가능 경우의 수 구하기
dfs(0, info_str.split(" "), new boolean[4]);
}
for (String key : map.keySet()) {
// 각 스펙별 점수 오름차순 정렬
Collections.sort(map.get(key));
}
int i = 0;
for (String str : query) {
String[] split = str.split(" ");
int validNum = Integer.parseInt(split[split.length - 1]);
String key = str.replaceAll("and| |[0-9]", "");
List<Integer> val = map.getOrDefault(key, null);
if (val != null) {
// query로 만든 key로 값을 찾을 수 있다면, 값 내에서 몇 번째인지 찾는다.
answer[i] = findManyPerson(val, validNum);
} else {
answer[i] = 0;
}
i++;
}
return answer;
}
int findManyPerson(List<Integer> val, int validNum) {
int left = 0;
int right = val.size();
while (left < right) {
int mid = (left + right) / 2;
if (val.get(mid) >= validNum) {
right = mid;
} else {
left = mid + 1;
}
}
return val.size() - left;
}
void dfs(int depth, String[] arr, boolean[] check) {
if (depth == 4) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < check.length; i++) {
boolean bool = check[i];
if (bool) {
sb.append(arr[i]);
} else {
sb.append("-");
}
}
String key = sb.toString();
if (map.containsKey(key)) {
map.get(key).add(Integer.valueOf(arr[4]));
} else {
map.put(key, new ArrayList<>(List.of(Integer.valueOf(arr[4]))));
}
return;
}
dfs(depth + 1, arr, check.clone());
check[depth] = true;
dfs(depth + 1, arr, check.clone());
}
}