2021 KAKO BLIND RECRUITMENT [순위 검색] [Javascript]

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

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

---

문제요약

1.최대 50000만명에 대해서 정보(개발언어 , 직군 , 경력 , 소울푸드 , 점수 ) 가 주어진다

2.쿼리는 최대 100,000개가 주어진다 (쿼리는 와일드카드가 포함될수 있는 형태)

3.쿼리에 만족하는 사람수를 배열에 담는다

---

나의 풀이

입출력 제한을 보고 무조건 전처리를 잘해놓고 쿼리에서 최소 logN으로 구해야겠다는 생각이 들었다.

 

 

와일드카드를 포함해서 나올수 있는 쿼리의 가짓수를 생각해 보았을때 이러한 형식으로 나오게 된다

개발언어	"java" , "cpp" , "python" ,"anything"
직군	"backend","frontend","anything"
경력	"junior","senior","anything"
소울푸드	"chicken","pizza","anything"

 점수까지는 가짓수를 나누기 어려우므로 나올수 있는 가짓수(4*3*3*3)개의 배열에 점수를 삽입하여 찾을때 이분탐색으로 찾는 생각을 하였다

 

info배열을 전처리 할때 총(2*2*2*2 만큼 anything의 가짓수도 생각을 해줘야됨) 의배열에 삽입이 일어난다

---

풀이과정

1.50000개 info 를 8개 배열에 push

2.모든 가짓수 (4*3*3*3) 배열을 sorting

3.쿼리가 오면 해당 쿼리에 맞게 배열을 선택하고 점수를 기준으로 이분탐색하여 사람이 몇명인지 계산

---

코드

	const Lan ={
	"-":0,
	"java":1,
	"cpp":2,
	"python":3,
	}
	const dep ={
	"-":0,
	"backend":1,
	"frontend":2
	}
	const car ={
	"-":0,
	"junior":1,
	"senior":2,
	}
	const food={
	"-":0,
	"chicken":1,
	"pizza":2,
	}
	function solution(info, query) {
	var answer = [];
	const Q ={};
	function lower_count(arr,val){
	if(arr==undefined)return 0;
	let low = 0;
	let high = arr.length;
	let mid;
	while (low < high) {
	mid = low + Math.floor((high - low)/2);
	if (val <= arr[mid]) {
	high = mid;
	} else {
	low = mid + 1;
	}
	}
	return arr.length-low;
	}
	let l=[0],d=[0],c=[0],f=[0];
	for(let i of info){
	let cur = i.split(" ");
	let score = parseInt(cur[4]);
	l.push(Lan[cur[0]]);
	d.push(dep[cur[1]]);
	c.push(car[cur[2]]);
	f.push(food[cur[3]]);
	for(let x of l){
	for (let y of d){
	for(let z of c){
	for(let w of f){
	let s = ""+x+y+z+w;
	if(!(s in Q)){
	Q[s]=[score];
	}else{
	Q[s].push(score);
	}
	}
	}
	}
	}
	l.pop();
	d.pop();
	c.pop();
	f.pop();
	}
	for(let i in Q){
	Q[i].sort((x,y)=>x-y);
	}
	for(let i of query){
	let cur = i.split(" ");
	let s = ""+Lan[cur[0]]+dep[cur[2]]+car[cur[4]]+food[cur[6]];
	answer.push(lower_count(Q[s],parseInt(cur[7])));
	}
	return answer;
	}

view raw .js hosted with ❤ by GitHub