2021 KAKAO BLIND RECRUITMENT 3번[검색 순위] 해설

programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

 

 

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})
        );
    }
}