카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.
코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.
인재영입팀에 근무하고 있는니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다. 예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다. 코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?
물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.
코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?
즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.
* [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?
[문제]
지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
info 배열의 크기는 1 이상 50,000 이하입니다.
info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
개발언어는 cpp, java, python 중 하나입니다.
직군은 backend, frontend 중 하나입니다.
경력은 junior, senior 중 하나입니다.
소울푸드는 chicken, pizza 중 하나입니다.
점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
query 배열의 크기는 1 이상 100,000 이하입니다.
query의 각 문자열은 "[조건] X" 형식입니다.
[조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
언어는 cpp, java, python, - 중 하나입니다.
직군은 backend, frontend, - 중 하나입니다.
경력은 junior, senior, - 중 하나입니다.
소울푸드는 chicken, pizza, - 중 하나입니다.
'-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.
문제 접근 방법
처음에 이문제를 보고 효율성은 생각하지 않은채 정확성만 생각하며 매우 쉽다생각하고 빠르게 풀었지만... 정확성은 다 맞지만 효율성 부분에선 전부 시간초과가 나왔다.
효율성 부분에서 계속 시간초과가 났던이유는 내가 만든 배열을 처음부터 끝까지 전부 하나하나 조건이 맞는지 조회하고 하나 조회끝나면 다시 조회하고... 무한반복을 해서 시간 초과가 난거라고 생각한다.
따라서 하나씩 전부 조회하는게 아니라 해당 조건 즉, 쿼리에 맞는 지원자들만 조회하고 점수조건이 맞는지만 확인하는 로직이 필요했다.
그에 따른 로직은 다음과 같다(다른 블로그들 참고함).
모든 지원자(info)들 한명씩 주어진 문자열을 조합해본다.("-"를 포함) 조합을 할때 주의할 점은 점수를 제외한 나머지값을 조합해야한다. 이게 무슨 말이냐면 "java backend junior pizza 150" <-- 이분의 경우
위의 사진과 같은 경우의 수가 나오게 된다.
이렇게 조합해야 하는 이유는 뭘까 생각해보면 간단하게 답을 찾을 수 있다. 만약 모든 지원자들에 대해 저런 조합을 하나씩 다 만들어보면서 만들었던 조합을 어딘가에 저장해 놓았을때 주어진 쿼리가 "java and backend and junior and pizza 100" 이라면 지원자들 중에서 점수를 제외한 나머지 조건인 "javabackendjuniorpizza" 를 무조건 찾을 수 있다.
그렇다면 한번에 탐색할수 있는 방법은? HashMap을 쓴다면 바로 탐색이 가능하다. 즉, 맵에 위의 사진에서 나온 모든 문자열 값들을 key로 저장해놓으면 쿼리에서 조건으로 나온 "javabackendjuniorpizza"를 map.containsKey("javabackendjuniorpizza")로 바로 탐색이 가능하다.
점수 저장 1번을 통해 위에서 조합된 문자열로 맵에 키값으로 저장해놨다. 그럼 점수는 어떻게 할까? 점수는 맵에서 key에 해당하는 value값으로 저장해 놓을 수 있다. 예를들어 info={"java backend junior pizza 150" , "java backend junior chicken 80"} 라고 한다면 첫번째와 두번째 요소의 조합을 살펴보면 "javabackendjunior--" 라는 똑같은 조합이 나온다. 이 조합이 map의 키값으로 저장돼있을때 value에 점수는 150,80을 넣어야 한다. 즉, 위의 값은 아래처럼 저장돼야 한다.
key
"javabackendjunior--"
value
150, 80
이렇게 저장하는 이유는 만약 쿼리가 "java and backend and junior and - and - 50" 이라면 위의 map에서 위의 키값을 탐색하고 그 키값의 value중 50점이 넘는 개수를 알수 있기 때문이다. 이 갯수는 결국 쿼리에 해당하는 지원자의 수가 된다.
지원자 카운트 1,2번 과정을 통해 info값을 map에 넣었다면 그맵과 쿼리 하나씩 조건을 비교하면서 현재 탐색중인 쿼리에 해당하는 지원자들을 카운트하고 answer에 넣어주면된다. 이때 주의할점은 key값을 찾고 점수조건을 탐색할때 이분탐색을 사용해야한다. 이유는 만약 info의 크기가 50000이라고 하면 조합의 수는 어마어마하게 많아진다. 따라서 빠른 탐색을 위해선 각 key에 해당하는 value값에대해 이분탐색이 필요하다.
여기까지 내가 다른 블로그들을 보고 로직을 구현하면서 이해한것들을 풀어 놓은것이다.
자세한 코드는 풀이를 보자.
풀이
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
public class Solution {
static HashMap<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>();
static int[] answer;
public static int[] solution(String[] info, String[] query) {
answer = new int[query.length];
//info의 요소 하나마다 "-"를 포함시켜 모든 조합의 경우의수를 만들기
for(int i=0; i<1; i++) {
dfs("", info[i].split(" "), 0);
}
for(String key:map.keySet()) {
System.out.println(key);
}
//위에서 모든 경우의수를 map에다 저장 후 맵에 저장돼있는
//각 key마다 value값을 오름차순 정렬시킴.
//오름차순 정렬시키는 이유는 countSQL 메서드에서 이분탐색을 위해서함.
for(String key:map.keySet()) {
Collections.sort(map.get(key));
}
//쿼리하나씩 탐색하면서 탐색하고 있는 쿼리에 맞는 지원자가 있다면
//answer에 해당 조건에 맞는 지원자 수 만큼 추가
for(int i=0; i<query.length; i++) {
//answer[i] = countSQL(query[i].replaceAll(" and", "").split(" "));
}
return answer;
}
//info의 모든 경우의 수("-"를 포함함)
public static void dfs(String str, String[] dfsInfo, int depth) {
if(depth==4) {
int score = Integer.parseInt(dfsInfo[4]);
if(map.containsKey(str)) {
map.get(str).add(score);
}else {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(score);
map.put(str, list);
}
return;
}
dfs(str+"-", dfsInfo, depth+1);//"-"를 포함한 조합
dfs(str+dfsInfo[depth], dfsInfo, depth+1);//"-"를 제외한 조합
}
//입력받은 쿼리요소 하나마다 해당하는 지원자가 몇명인지 카운트
public static int countSQL(String[] sql) {
String key = "";
int score = 0;
//map의 key값과 value값 비교를 위해
//입력받은 쿼리를 key값과 score값으로 나눔.
for(int i=0; i<sql.length; i++) {
if(i!=sql.length-1) key += sql[i];
else score = Integer.parseInt(sql[i]);
}
//map에 해당 키(지원자)가 있다면
if(map.containsKey(key)) {
ArrayList<Integer> list = map.get(key);
int low = 0;
int mid = 0;
int high = list.size()-1;
//이분탐색
while(low <= high) {
mid = (low+high)/2;
if(list.get(mid) < score) {
low = mid+1;
}else {
high = mid-1;
}
}
//key값에 해당하는 전체 지원자 - 쿼리에서 요구하는 최소 점수의 인덱스
//즉, 최소 점수가 해당하는 인덱스 위로는 전부
//쿼리에서 요구하는 점수보다 큰 점수를 갖고있는 지원자들임.
return list.size()-low;
}
//해당하는 지원자 없으면 0명 반환.
return 0;
}
}
마치며
효율성을 생각하면 쉽게 로직이 떠오르지않아 나는 어려운 문제였다고 생각한다. 하지만 다른 블로그들을 참고하며 많은 공부가 됐던 문제다.
