▷ 문제 : 2021 KAKAO BLIND RECRUITMENT - 순위 검색 LV. 2
코딩테스트 연습 - 순위 검색
["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"] ["java and backend and junior and pizza 100","pyt
programmers.co.kr
▷ 해결 날짜 : 2022.03.26
▷ 소요 시간 : 1시간 (2차 시도)
▷ 풀이 과정 :
문제 자체는 금방 이해했다. 핵심도 정리해서 문제에 주니 정말 쉬워 보였는데... 일단 다음 조건을 만족하기만 하면 된다.
* [조건]을 만족하는 사람 중 코딩 테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?
이 조건만 가지고 문제를 풀라고해서 20분 만에 문제를 해결했는데
function solution(info, query) {
return query.map(e => {
const condition = e.split(' ').filter(e => e != '-' && e != 'and');
const score = Number(condition.splice(-1));
return info.filter(v1 => condition.every(v2 => v1.includes(v2)) && v1.match(/\d/g).join('') >= score).length;
});
}아니나 다를까 "효율성 테스트" 문제였다.
당연히 효율성 부분에서 0점이 나와서 통과를 하지 못했는데, 몇 시간을 개선하다가 이렇게 풀면 도저히 안될 거 같아 몇몇 글을 통해 도움을 받았다.
이 테스트의 핵심은 해시와 이진탐색 알고리즘을 사용하여 푸는 것이다.
그래서 일단 이진 탐색 알고리즘을 모르기 때문에 공부하고 나서 다시 풀어 해결했다.
1. "java backend junior pizza 150" 이러한 값이 주어졌다면 "javabackendjuniorpizza" 이렇게 점수를 제외한 나머지를 합쳐서 하나의 key로 등록하고 value로는 점수를 등록하는 과정을 통해 1차적으로 데이터를 정제하여야 한다.
2. 그리고 이진 탐색을 위해 다시 한번 value값들을 오름차순으로 정렬을 해야 한다.
3. 그다음 이제 검색 쿼리 파라미터 "- and backend and senior and - 150" 가 주어진다면 해당 조건에 맞는 것들만 스캔하여 개수를 찾아주면 된다.
(여기서 "-" 는 문제를 보면 알겠지만 어떤 값이든 상관없다는 의미이다.)
3-1. "and", " ", "-" 를 기준으로 전부 잘라서 사용하였다. (결국 주어진 값들만 체크하면 되는 것이기 때문에)
3-2. 그리고 이진 탐색은 주어진 score와 같은 값을 찾는 게 아니라 이상인 것들을 찾는 거라 Lowerbound 알고리즘을 사용하였다.
▷ 구현
function solution(infos, querys) {
const rule = new Map();
infos.forEach(v => {
const info = v.split(' ');
const score = Number(info.pop());
let key = info.join('');
rule.set(key, rule.has(key) ? [...rule.get(key), score] : [score]);
});
for(let [key, value] of rule){
rule.set(key, value.sort((a, b) => a - b));
}
return querys.map(e => {
const conditions = e.split(/ and | |-/i).filter(e => e);
return search(rule, conditions);
});
}
const search = (rule, conditions) => {
const score = conditions.pop();
return Array.from(rule.keys())
.filter(key => conditions.every(v => key.includes(v)))
.reduce((a, c) => a + rule.get(c).slice(lowerBound(rule.get(c), score)).length, 0);
}
const lowerBound = (arr, target) => {
let left = 0;
let right = arr.length;
while(left < right){
const mid = Math.floor((left + right) / 2);
if(arr[mid] >= target) right = mid;
else left = mid + 1;
}
return left;
}
▷ 복기 :
이게... 2단계? 근데 질문하기 탭을 들어가 보면 아무래도 체감상 3단계 난이도 정도는 되는 것 같다.
그리고 카카오 해설본이 있는데, 이 문제는 나처럼 푸는 게 아니라 "-"를 포함한 모든 경우의 수를 미리 구해두고 거기서 뽑아 쓰는 방식을 사용해야 한다고 한다.
카카오 해설 방식으로 안 풀어봐서 모르겠지만 아무래도 그게 더 성능이 잘 나올 것 같긴 하다.
(그도 그럴게 분명 통과된 코드인데 다시 실행하면 가끔 시간 초과 뜬다 환장.. 그렇다고 다시 풀긴 싫다 하하)
댓글