import java.util.*;
class Solution {
private static List<Integer> ansList = new ArrayList<>();
public int[] solution(String[] info, String[] query) {
//info 최대 50,000 query 최대 100,000 50억 안될듯
Info[] infos = new Info[info.length];
int k = 0;
for(String s : info){
infos[k++] = new Info(s);
}
Query[] queries = new Query[query.length];
k=0;
for(String s : query){
queries[k++] = new Query(s);
}
//점수를 기준으로 정렬해서 이분탐색을하자. ?점 이상인걸 찾으면된다. [ )
//정렬한다.
Arrays.sort(infos);
//목표스코어 이상인걸 모두 찾으면 된다. 정보들 중에서
for(Query q : queries){
int targetScore = q.score;
int lowerIdx = binarySearch(targetScore, infos);
int count = 0;
for(int i = lowerIdx ; i<infos.length ; i++){
Info in = infos[i];
if(q.language.equals(in.language)
&& q.jobKind.equals(in.jobKind)
&& q.carrer.equals(in.carrer)
&& q.soulFood.equals(in.soulFood)
) ++count;
}
ansList.add(count);
}
int[] ans = new int[ansList.size()];
for(int i =0 ; i<ans.length ; i++){
ans[i] = ansList.get(i);
}
return ans;
}
//내가 필요한건 조건을 만족하는 값중 가장 작은 값의 인덱스. 이 인덱스로 증가시키면서 갱신하면됨...
//LOWER BOUND
private static int binarySearch(int targetScore, Info[] infos){
int start = 0; // 포함
int end = infos.length ; // 제외
while(start < end){
int mid = (start + end) / 2;
int currentScore = infos[mid].score;
//end가 포함안된다는게 뭔소리지...
//목표 점수보다 현재 점수가 더 크다 -> 범위를 좌측으로 옮긴다.
if(targetScore < currentScore){
end = mid + 1;
}
//목표 점수보다 현재 점수가 더 작다 -> 범위를 우측으로 옮긴다.
else if(targetScore > currentScore){
start = mid;
}
//같다면... ( ]
else{
start = mid;
}
}
return end;
}
private static class Info implements Comparable<Info>{
public String language;
public String jobKind;
public String carrer;
public String soulFood;
public int score;
Info(String info){
String[] split = info.split(" ");
language = split[0];
jobKind = split[1];
carrer = split[2];
soulFood = split[3];
score = Integer.parseInt(split[4]);
}
@Override
public int compareTo(Info other){
return this.score - other.score;
}
}
private static class Query{
public String language;
public String jobKind;
public String carrer;
public String soulFood;
public int score;
Query(String query){
String[] split = query.split(" and ");
language = split[0];
jobKind = split[1];
carrer = split[2];
soulFood = split[3].split(" ")[0];
score = Integer.parseInt(split[3].split(" ")[1]);
}
}
}
몇시간 헤맨 결과물
import java.util.*;
class Solution {
private static Map<String,List<Integer>> map = new HashMap<>();
public int[] solution(String[] info, String[] query) {
//info를 인덱싱? 해놓는다.
Info[] infos = new Info[info.length];
for(int i = 0 ; i<info.length ; i++){
infos[i] = new Info(info[i]);
indexingInfo(infos[i]);
}
for(List<Integer> scoreList : map.values()){
scoreList.sort(Comparator.naturalOrder());
}
//여태까지는 전처리 과정이다.
int[] answer = new int[query.length];
for(int i=0 ; i < query.length ; i++){
if(map.get(extractKey(query[i])) == null){
answer[i] = 0;
continue;
}
List scoreList = map.get(extractKey(query[i]));
// scoreList.sort(Comparator.naturalOrder()); 여기서 하지 않는다!
// int lowerIdx = binarySearch(query[i].socre, infos);
int lowerIdx = binarySearch(extractScore(query[i]), scoreList);
answer[i] = scoreList.size() - lowerIdx;
}
return answer;
}
//내가 필요한건 조건을 만족하는 값중 가장 작은 값의 인덱스. 이 인덱스로 증가시키면서 갱신하면됨...
//LOWER BOUND
private static int binarySearch(int targetScore, List<Integer> scores){
int start = 0; // 포함
int end = scores.size() ; // 제외
while(start < end){
int mid = (start + end) / 2;
int currentScore = scores.get(mid);
//end가 포함안된다는게 뭔소리지...
//목표 점수보다 현재 점수가 더 크다 -> 범위를 좌측으로 옮긴다.
if(targetScore <= currentScore){
end = mid;
}
else{
start = mid+1;
}
}
return end;
}
private static String extractKey(String query){
query = query.replaceAll(" and ","");
return query.split(" ")[0];
}
private static int extractScore(String query){
query = query.replaceAll(" and ","");
return Integer.parseInt(query.split(" ")[1]);
}
private static void indexingInfo(Info info){
for(String key : info.keys){
map.putIfAbsent(key,new ArrayList<>());
map.get(key).add(info.score);
}
}
private static class Info implements Comparable<Info>{
public String language;
public String jobKind;
public String carrer;
public String soulFood;
public int score;
public String[] keys = new String[16];
Info(String info){
String[] split = info.split(" ");
keys[0] = split[0] + split[1] + split[2] + split[3];
keys[1] = "-" + split[1] + split[2] + split[3];
keys[2] = split[0] + "-" + split[2] + split[3];
keys[3] = split[0] + split[1] + "-" + split[3];
keys[4] = split[0] + split[1] + split[2] + "-";
keys[5] = "-" + "-" + split[2] + split[3];
keys[6] = "-" + split[1] + "-" + split[3];
keys[7] = "-" + split[1] + split[2] + "-";
keys[8] = split[0] + "-" + "-" + split[3];
keys[9] = split[0] + "-" + split[2] + "-";
keys[10] = split[0] + split[1] + "-" + "-";
keys[11] = "-" + "-" + "-" + split[3];
keys[12] = "-" + "-" + split[2] + "-";
keys[13] = "-" + split[1] + "-" + "-";
keys[14] = split[0] + "-" + "-" + "-";
keys[15] = "-" + "-" + "-" + "-";
score = Integer.parseInt(split[4]);
}
@Override
public int compareTo(Info other){
return this.score - other.score;
}
}
private static class Query{
public String language;
public String jobKind;
public String carrer;
public String soulFood;
public int score;
Query(String query){
String[] split = query.split(" and ");
language = split[0];
jobKind = split[1];
carrer = split[2];
soulFood = split[3].split(" ")[0];
score = Integer.parseInt(split[3].split(" ")[1]);
}
}
}