문제
문제 풀이
효율성 통과를 위해서는 조합과 이진 탐색이 핵심이었다.
-
info 데이터 전처리ex) "java and backend and junior and pizza 100"
>infos = ['java', 'backend', 'junior', 'pizza']
>score = 100 -
combination()
info > infos를 순회하면서 "-"가 들어갈 수 있는 조합을 모두 구하여 Map객체로 변환한다. 조합은 key로 코테 점수는 value로 설정하되 배열 형태로 저장한다.value를 배열형태로 저장하는 이유
info를 순회하다보면 항목별로 "-"로 치환되기 때문에 같은 key가 생성될 수 있다. 따라서 배열형태의 value에 점수를 추가해가는 방식으로 구현한 것이다.key value javabackendjuniorpizza [150] -backendjuniorpizza [150] java-juniorpizza [150] javabackend-pizza [150] javabackendjunior- [150] --juniorpizza [150] -backend-pizza [150] -backendjunior- [150] java--pizza [150] java-junior- [150] javabackend-- [150] ---pizza [150] --junior- [150] java--- [150] ---- [150]
- 항목
언어(4) : cpp, java, python, -
직군(3) : backend, frontend, -
경력(3) : junior, senior, -
푸드(3) : chicken, pizza, -
- 모든 가능한 조합 : 108개 (4*3^3)
-
점수(infoMap[key], value) 정렬
이진 탐색 전 정렬 필수 !!!
-
query 데이터 전처리ex) "java and backend and junior and pizza 100"
> ['javabackendjuniorpizza', '100']
>key = 'javabackendjuniorpizza'
>score = 100
lowerboundSearch()
지원자 점수 목록 scores(value)에서 score값 이상의 점수에 대한 하한선을 이진 탐색한다. 하한선 탐색으로 일반 이진 탐색 코드와 차이 있음 주의score 이상의 점수를 받은 사람이 몇명인지 구하기 위해 구한 인덱스를 배열 길이에서 뺀다.
>scores.length - low
> answer.push(scores.length - low)
최종 코드
function solution2(info, query) { // 방법 2 : 정확성 통과 O, 효율성 통과 O
let answer = [];
let infoMap = {};
// 2. 한 info에 대해서 가능한 모든 조합 구하기
function combination(infos, score, start){
const key = infos.join(""); // 키 값으로 사용할 조건 이어붙이기
const value = infoMap[key]; // 점수
// 2.1. 현재 조합에 점수 저장
if(value){ // 해당 조건에 점수가 존재하는 경우, 점수 배열에 현재 점수 삽입
infoMap[key].push(score);
}
else{ // 아직 점수가 없는 경우, 현재 점수 값으로 초기화
infoMap[key] = [score];
}
// 2.2. 그 다음 조합 생성(단, - 를 이용해서 조합 생성)
for(let i = start; i < infos.length; i++){
let tmp = infos.slice();
tmp[i] = '-';
combination(tmp, score, i+1);
}
}
// // 5. 지원자 점수 목록 scores에서 score값 이상의 점수에 대한 하한선을 이진 탐색
function lowerboundSearch(scores, score){
if(scores){ // 검색 조건에 해당하는 지원자가 존재하는 경우(점수가 존재할 경우)에만 탐색 진행
let low = 0;
let high = scores.length;
while(low < high){
const mid = Math.floor((low + high)/2);
if(scores[mid] >= score){
high = mid;
}
else{
low = mid + 1;
}
}
answer.push(scores.length - low);
}
else{ // 검색 조건에 해당하는 지원자가 존재하지 않는 경우 0명으로 초기화
answer.push(0);
}
}
// 1. info 데이터 전처리
for(let i = 0; i < info.length; i++){
const infos = info[i].split(' ');
const score = +(infos.pop());
combination(infos, score, 0);
}
// 3. infoMap 이진 탐색 전 정렬 필수 !
for (const key in infoMap) {
infoMap[key] = infoMap[key].sort((a, b) => a - b);
}
// 4. query 데이터 전처리
for(let i = 0; i < query.length; i++){
let querys = query[i].replace(/ and /g, '').split(' ');
const score = +(querys.pop());
const key = querys.join('');
lowerboundSearch(infoMap[key], score);
}
return answer;
}처음에 작성한 코드
구글링 없이 풀었을 때의 코드이다. 정확성은 통과했지만 시간초과로 효율성 통과하지 못했다. 위 코드와 차이점은 다음과 같다.
-
query 데이터를 전처리를 하는 과정에서 '-'인 요소는 어떤 값이 오든 상관이 없기 때문에 필요 없는 값이라고 생각해서 모두 제거했다.
-
Map 객체로 변환하지 않고, querys와 infos(전처리한 데이터)를 반복문 돌려서 비교했다.
-
특정 쿼리에 대해서 각 infos마다 쿼리에서 요구하는 모든 요소('-'제거한 모든 항목)를 포함하고 있는지 검사했다.
function solution1(info, query) { // 방법 1 : 정확성 통과 O, 효율성 통과 X
let answer = [];
// 1. 데이터 전처리
// info
let infos = info.map(x=>x.split(' '));
// query
let querys = query.map(x=>x.split(' and '));
querys = querys.map(x=>[x[0], x[1], x[2]].concat(x[3].split(" ")));
querys = querys.map(x=>x.filter(y=>y != '-'));
// 2. 조건 충족 여부 검사
for(let j = 0, qLen = querys.length; j < qLen; j++){
answer.push(0); // j번 째 쿼리에 만족하는 지원자 수
const arr = [...querys[j]];
const score = +arr.pop(); // 현재 info에서 점수 제외
for(let k = 0, kLen = infos.length; k < kLen; k++){
const target_score = +infos[k][infos[k].length - 1];
if (score <= target_score) // 쿼리 점수 이상을 받은 지원자인 경우
if(arr.filter(x => !infos[k].includes(x)).length == 0) // 조건을 만족하는지 검사
answer[answer.length - 1]++;
}
}
return answer;
}문제점 및 해결방안
지금까지 풀었던 문제 중에서 역대급으로 어려웠던 문제였다. 문법적인 에러는 발생하지 않았는데, 기댓값[1,1,1,1,2,4]이 출력되지 않는 에러가 발생했다. 두가지 원인이 있었고 다음과 같이 해결했다.
- 이진 탐색 전에 정렬을 안 함
-> 정렬 코드 추가for (const key in infoMap) { infoMap[key] = infoMap[key].sort((a, b) => a - b); } - 점수를 숫자타입으로 바꾸지 않음
- score = querys.pop() ->+(querys.pop()) 수정
