프로그래머스 순위 검색 [2021 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/72412
효율성 테스트를 통과하지 못해 꽤 오랜 시간 고민했던 문제.
정확도만 바라보고 구현한다면 심플한 접근이 가능한 만큼, 효율성 테스트가 만만치 않음을 상기시켜주었다.
.
.
주어진 질문은 다음과 같다.
[조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?
이 질문을 두 단계로 나누어 보자면,
- [조건]을 만족하는 사람을 필터링한 뒤
- 그 중 X점 이상을 받은 사람의 수를 센다.
혹은 반대로
- X점 이상을 받은 사람 중
- [조건]을 만족하는 사람의 수를 센다.
라는 방식으로 접근하려 할 수도 있다.
.
.
나의 경우, 첫 시도에 두 번째 방법으로 접근했었다.
모든 지원자들을 점수 순으로 Sorting한 뒤, Binary Search로 X점 이상을 받은 사람 목록을 추출했다. 이 중 조건을 만족하는 사람을 일일히 세고자 한 것이다.
조건을 만족하는 지 판별할 때 모든 지원자에 대해 하나하나 비교한다는 한계점이 자명했다.
query마다 X점 이상을 받은 참석자들의 조건을 하나하나 비교했고, 결국 효율성 테스트에서 실패하고 말았다.
query가 100,000개까지, 지원자가 50,000명까지 올 수 있고, 네 가지 조건에 대해 모두 확인해야 하므로 수행시간이 압도적으로 길 수 밖에 없었다.
.
.
그래서 시도한 두 번째 방법은, query에서 주어질 수 있는 모든 조건에 대해 만족하는 지원자 목록을 미리 만들어 두는 것. 그리고 이 중 X점 이상을 받은 참석자들의 수를 Binary Search로 알아내는 것이다.
모든 조건에 대해 지원자 목록을 미리 만들어둔다는 점에서 꽤나 거부감이 있었던 접근방식이었으나,
모든 조건이라고 해 봐야 4*3*3*3 = 108가지밖에 되지 않는다.
그리고 지원자 한 명이 만족할 수 있는 조건은 2*2*2*2 = 16가지.
지원자가 50,000명까지 가능하다는 점까지 고려해보자.
100,000개의 query에 대해 일일히 조건비교를 하는 위의 방법보다 압도적으로 시간을 절약할 수 있다.
import java.util.*;
class Solution {
private static Map<String, List<Integer>> conditionMap = new HashMap<>();
private static final String[] langArr = {"-", "cpp", "java", "python"};
private static final String[] groupArr = {"-", "backend", "frontend"};
private static final String[] expArr = {"-", "junior", "senior"};
private static final String[] foodArr = {"-", "chicken", "pizza"};
private class Applicant implements Comparable<Applicant>{
private String[] condition = new String[4];
private int score;
public Applicant(String[] condition, int score){
this.condition = condition;
this.score = score;
}
@Override
public int compareTo(Applicant app){
if(this.score < app.score) return -1;
if(this.score > app.score) return 1;
return 0;
}
}
public int[] solution(String[] infos, String[] query) {
int[] answer = new int[query.length];
Applicant[] applicants = new Applicant[infos.length];
for(int i = 0 ; i < infos.length ; i++){
String[] infoArr = infos[i].split(" ");
applicants[i] = new Applicant(Arrays.copyOfRange(infoArr, 0, 4), Integer.parseInt(infoArr[4]));
}
Arrays.sort(applicants);
initConditionMap();
for(Applicant app : applicants)
dfs(app.condition, 0, "", app.score);
for(int i = 0 ; i < query.length ; i++){
query[i] = query[i].replaceAll("and ", "");
String[] conditionArr = query[i].split(" ");
String condition = "";
for(int j = 0 ; j < 4 ; j++)
condition += conditionArr[j] + " ";
int standard = Integer.parseInt(conditionArr[4]);
int applicant = binarySearch(0, conditionMap.get(condition).size()-1, standard, conditionMap.get(condition));
if(applicant >= 0){
answer[i] = conditionMap.get(condition).size() - applicant;
} else answer[i] = 0;
}
return answer;
}
public int binarySearch(int startIndex, int endIndex, int standard, List<Integer> scoreList){
if(scoreList.size() == 0 || scoreList.get(endIndex) < standard) return -1;
if(startIndex >= endIndex) return startIndex;
int midIndex = (startIndex + endIndex)/2;
if(scoreList.get(midIndex) < standard) startIndex = Math.min(endIndex, midIndex+1);
else endIndex = midIndex;
return binarySearch(startIndex, endIndex, standard, scoreList);
}
public void initConditionMap(){
for(String lang : langArr)
for(String group : groupArr)
for(String exp : expArr)
for(String food : foodArr)
conditionMap.put(lang + " " + group + " " + exp + " " + food + " ", new ArrayList<>());
}
public void dfs(String[] condition, int index, String key, int score){
if(index == 4){
conditionMap.get(key).add(score);
} else {
dfs(condition, index+1, key + condition[index] + " ", score);
dfs(condition, index+1, key + "-" + " ", score);
}
}
}
