2021.08.17
문제명 : 2021 KAKAO BLIND RECRUITMENT 순위 검색
사용언어 : Javascript
개발 시간 : 120분 + 다른 사람 풀이 60분
코딩테스트 연습 - 순위 검색
["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
📋 문제 설명
이 문제의 핵심은 조합과 이분탐색입니다.
주어진 info 배열이 가질 수 있는 조합을 모두 구하고
이분탐색을 이용해 query 배열의 조건에 맞는 갯수를 구하는 것입니다.
이분 탐색의 간단한 예시를 먼저 보고 갑시다.
1 2 3 4 5 6라는 값에서 6을 찾고자 한다면
배열의 중간에 위치한 3이라는 값과 6을 비교합니다.
6은 3보다 크므로, 이제 3의 왼쪽에 위치하는 값들은 탐색할 필요가 없으므로
(어차피 3 왼쪽에 있는 수들은 3보다 작기 때문입니다)
3의 오른쪽에 있는 값들을 대상으로 탐색을 다시 시도합니다.
이제 4 5 6이 남았으므로, 다시 중간값인 5와 찾고자 하는 대상인 6를 비교합니다.
6은 5보다 크므로, 5의 오른쪽에 있는 값들을 대상으로만 탐색을 다시 시도합니다.
이제 6만이 남았는데 6과 6을 비교하면, 값이 일치하므로 탐색을 종료합니다.
출처: https://satisfactoryplace.tistory.com/39
우선 조합을 통해서 - 를 다 넣어줍니다.
예를 들어,
java backend junior pizza 150 이 입력으로 들어왔다고 칩시다.
- backend junior pizza 150
java - junior pizza 150
java backend - pizza 150
java backend junior - 150
.
.
.
- - - - 150
이런식으로 -를 넣을 수 있는 곳을 조합으로 찾아 모두다 150을 넣어줍니다.
출처 : https://dkwjdi.tistory.com/224
📢 입출력 예
🔑 문제 풀이
// 정확성 테스트 success
// 효율성 테스트 success
function solution(info, query) {
var answer = [];
let map = {};
function combination(infos, score, map, start){
let key = infos.join(""); // 키 값으로 쓸거 합쳐주기
let value = map[key]; // 값 있는지 없는지 확인해주기
if(value){ // 값이 있으면 push
map[key].push(score);
}else{ // 값이 없으면 프로퍼티 만들어주기
map[key] = [score];
}
// -를 이용해 조합 만들기
for(let i=start; i<infos.length; i++){
let combiArr = [...infos]; // 전개연산자 ...
combiArr[i] = '-';
combination(combiArr, score, map, i+1);
}
}
// 이분탐색
function binarySearch(map2, key2, score2){
let scoreArr = map2[key2];
if(scoreArr){
var start = 0;
var end = scoreArr.length;
while(start < end){
var mid = Math.floor((start+end)/2);
if(scoreArr[mid] >= score2){ // 현재 가르키는 값보다 내가 찾는 값이
end = mid;
}else if(scoreArr[mid] < score2){
start = mid + 1;
}
}
return scoreArr.length - start;
}
else return 0
}
// 1. -로 가능한 모든 조합 만들기
for(let i=0; i<info.length; i++){
let infos = info[i].split(" ");
let score = infos.pop();
combination(infos, score, map, 0);
}
// 2. 이분탐색을 위해 정렬
for(let key in map){
map[key].sort((o1, o2) => o1 - o2);
}
// 3. 이분탐색 실행
for(let i=0; i<query.length; i++){
let querys = query[i].replace(/ and /g, "").split(" ");
let score = Number(querys.pop());
answer.push(binarySearch(map, querys.join(""), score));
}
return answer;
}
// 정확성 테스트 success
// 효율성 테스트 fail
function solution(info, query) {
var answer = [];
var arr1 = [];
var arr2 = [];
for(var i=0; i<info.length; i++){
arr1.push(info[i].split(' '));
}
for(var i=0; i<query.length; i++){
arr2.push(query[i].replace(/and /gi,'').split(' '));
}
for(var i=0; i<arr2.length; i++){
var cnt = 0;
for(var j=0; j<arr1.length; j++){
for(var k=0; k<4; k++){
if(arr2[i][k] == arr1[j][k] || arr2[i][k] == '-'){
if(k==3 && arr2[i][4]*1 <= arr1[j][4]*1){
cnt++;
}
}else{
break;
}
}
}
answer.push(cnt);
}
return answer;
}
🔔 새로 알게 된 점
2단계가 맞나 싶을 정도로 난이도가 높게 느껴졌다.
첫 시도때는 점수를 제외한 조건들만 차례대로 비교하면서 충족할 경우에만 점수를 비교하였다.
이렇게 풀면 정답이긴 하나, 효율성 테스트에서 fail이 뜬다.
for문이 중첩되면서 타임아웃 에러가 나는 듯 하다.
다른 사람의 풀이를 참조하니 이분탐색을 이용하지 않으면 통과할 수 없는 문제같다.
조합, 이분탐색, 프로퍼티 등을 공부하고 알고리즘을 이해하는 것이 중요할 듯 하다.
프로퍼티 관련 : https://opentutorials.org/module/3989/26100
