[프로그래머스] 순위 검색
문제
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72412
내 코드
function solution(info, query) {
var answer = [];
for(let i=0; i<query.length; i++){
let cnt = 0;
let q = query[i].split(' and ');
let tmp = q[3].split(' ');
q = q.slice(0,3).concat(tmp[0]);
let score = tmp[1];
for(let j=0; j<info.length; j++){
let inf = info[j].split(' ');
if(check(inf,q,Number(score))) cnt++;
}
answer.push(cnt);
}
return answer;
}
function check(info,query,score){
if(Number(info[4]) < score) return false;
let check = false;
for(let i=0; i<info.length-1; i++){
if(info[i]===query[i] || query[i]==='-'){
check = true;
}else{
return false;
}
}
return check;
}
나름 효율 챙겨보겠다고 노력해봤으나 결과는
…
다른 사람의 코드
function solution(info, query) {
const answer = [];
const infoMap = {};
function combination(array, score, start) {
const key = array.join("");
const value = infoMap[key];
if (value) {
infoMap[key].push(score);
} else {
infoMap[key] = [score];
}
for (let i = start; i < array.length; i++) {
const temp = [...array];
temp[i] = "-";
combination(temp, score, i + 1);
}
}
for (const e of info) {
const splited = e.split(" ");
const score = Number(splited.pop());
combination(splited, score, 0);
}
for (const key in infoMap) {
infoMap[key] = infoMap[key].sort((a, b) => a - b);
}
for (const e of query) {
const splited = e.replace(/ and /g, " ").split(" ");
const score = Number(splited.pop());
const key = splited.join("");
const array = infoMap[key];
if (array) {
let start = 0;
let end = array.length;
while (start < end) {
const mid = Math.floor((start + end) / 2);
if (array[mid] >= score) {
end = mid;
} else if (array[mid] < score) {
start = mid + 1;
}
}
const result = array.length - start;
answer.push(result);
} else {
answer.push(0);
}
}
return answer;
}
Map 을 사용해서 효율을 높여야 되는것 같다.