2021 KAKAO BLIND RECRUITMENT 3번[검색 순위] 해설
programmers.co.kr/learn/courses/30/lessons/72412
코딩테스트 연습 - 순위 검색
["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
1. 분류
이분탐색
2. 풀이
문제 자체를 이해하기는 어렵지 않다.
데이터베이스를 활용해 본 경험이 있다면 이 문제가 아래의 쿼리 결과를 요구한다는 것을 바로 눈치챌 수 있을 것이다.
-- INPUT에서 데이터 삽입
INSERT INTO TABLE(LANGUAGE, POSITION, LEVEL, FOOD, SCORE)
VALUES (${language}, ${position}, ${level}, ${food}, ${score});
-- 주어진 query로 개수 탐색
SELECT count(*)
FROM TABLE
WHERE [language = 'java', position = 'backend' 등 주어진 조건에 따라 가변처리]
AND SCORE >= ${score}정말 쉽다. DB를 쓸 수 있다면 5분도 걸리지 않을 문제이다.
하지만 코드로만 구현해야 하는 제약조건에서 "-" 으로 주어지는 dont care 조건을 어떻게 구현해야 할까를 고민해야 한다.
데이터는 List<Integer>[LANGUAGE][POSITION][LEVEL][FOOD]에 넣는다.
인덱스를 순서대로 기입함에 주의한다.
dont care를 찾아내기 위한 가장 쉬운 답은 dont care 데이터까지 함께 삽입해버리는 것이다.
예를 들어 [java backend junior chicken 300]이라는 데이터를 받았다고 한다면,
java, backend, junior, chicken (원본)
java, backend, junior, * (*은 dont care)
java, backend, *, chicken
java, backend, *, *
java, *, junior, chicken
java, *, junior, *
java, *, *, chicken
java, *, *, *
*, backend, junior, chicken
*, backend, junior, *
*, backend, *, chicken
*, backend, *, *
*, *, junior, chicken
*, *, junior, *
*, *, *, chicken
*, *, *, *이렇게 16개의 데이터를 함께 삽입해버린다.
쿼리가 java and - and - and - 150으로 주어지면
list[JAVA_INDEX][DONTCARE_INDEX][DONTCARE_INDEX][DONTCARE_INDEX]를 찾아내면 되는 것이다.
모든 데이터를 삽입하고 난 뒤엔 모든 List를 오름차순으로 정렬한다.
350점 이상을 찾으려고 할 때, 같은 조건 안에 350점이 여러 명 있을수도 있고 350점이 없을수도 있다.
정렬된 리스트에서 이진 탐색으로 적절한 값을 찾되, 그 중에서도 가장 왼쪽의 인덱스를 얻어내기 위해서는 lower bound를 사용하면 된다.
3. 소스코드
풀이
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
class Solution {
private final ArrayList<Integer>[][][][] database = new ArrayList[4][3][3][3];
public int[] solution(String[] infos, String[] queries) {
Arrays.stream(infos)
.forEach(this::insert);
sortDatabase();
return Arrays.stream(queries)
.mapToInt(this::search)
.toArray();
}
private void insert(String info) {
String[] column = split(info);
int[] indexes = new int[4];
for (int i = 0; i < 4; i++) {
indexes[i] = Constant.findIndex(column[i]);
}
int score = Integer.parseInt(column[4]);
int dontCare = Constant.DONT_CARE.index;
for (int i = 0; i < 16; i++) {
int idx0 = (i & 1) == 1 ? dontCare : indexes[0];
int idx1 = (i & 2) == 2 ? dontCare : indexes[1];
int idx2 = (i & 4) == 4 ? dontCare : indexes[2];
int idx3 = (i & 8) == 8 ? dontCare : indexes[3];
addScore(idx0, idx1, idx2, idx3, score);
}
}
private void sortDatabase() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
for (int l = 0; l < 3; l++) {
if (database[i][j][k][l] != null) {
Collections.sort(database[i][j][k][l]);
}
}
}
}
}
}
private int search(String query) {
String[] data = split(query);
int language = Constant.findIndex(data[0]);
int position = Constant.findIndex(data[2]);
int level = Constant.findIndex(data[4]);
int food = Constant.findIndex(data[6]);
int score = Integer.parseInt(data[7]);
return binarySearch(database[language][position][level][food], score);
}
private int binarySearch(List<Integer> list, int score) {
if (list == null || list.size() == 0) {
return 0;
}
if (list.size() == 1) {
if (score <= list.get(0)) {
return 1;
}
return 0;
}
int left = 0;
int right = list.size();
while (left < right) {
int middle = (left + right) / 2;
if (list.get(middle) < score) {
left = middle + 1;
} else {
right = middle;
}
}
return list.size() - left;
}
private void addScore(int idx0, int idx1, int idx2, int idx3, int score) {
if (database[idx0][idx1][idx2][idx3] == null) {
database[idx0][idx1][idx2][idx3] = new ArrayList<>();
}
database[idx0][idx1][idx2][idx3].add(score);
}
private String[] split(String s) {
return s.split(" ");
}
enum Constant {
ERROR(null, -1),
DONT_CARE("-", 0),
CPP("cpp", 1),
JAVA("java", 2),
PYTHON("python", 3),
BACKEND("backend", 1),
FRONTEND("frontend", 2),
JUNIOR("junior", 1),
SENIOR("senior", 2),
CHICKEN("chicken", 1),
PIZZA("pizza", 2);
private static final Map<String, Constant> ALL_MAP =
Arrays.stream(values())
.collect(Collectors.toMap(c -> c.value, Function.identity()));
String value;
int index;
Constant(String value, int index) {
this.value = value;
this.index = index;
}
public static int findIndex(String key) {
return ALL_MAP.getOrDefault(key, ERROR).index;
}
}
}ALL_MAP은 문자열 비교 시간을 아끼기 위해 (Constant.value, Constant)를 map으로 미리 구성했다.
map에서 찾아오기 때문에 이 문제에서 모든 문자열을 탐색하는 시간은 O(1)으로 고정된다. (문자열로 해시값을 만드는 시간 제외)
실무에서도 상수성 데이터를 지속적으로 비교하는 경우 굉장히 유용한 테크닉이다.
테스트 (실행)
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
import java.util.Arrays;
import java.util.stream.Stream;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;
class SolutionTest {
private final Solution s = new Solution();
@MethodSource("testcase")
@ParameterizedTest
void test(String[] infos, String[] queries, int[] output) {
var result = s.solution(infos, queries);
System.out.println("result: " + Arrays.toString(result));
System.out.println("output: " + Arrays.toString(output));
assertThat(result, is(output));
}
private static Stream<Arguments> testcase() {
return Stream.of(
Arguments.of(
new String[] {"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"},
new String[] {"java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"},
new int[] {1,1,1,1,2,4})
);
}
}