[Programmers] 순위 검색 (Java, Kotlin)

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

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

문제

 

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어집니다. 각 문의조건에 해당하는 사람들이ㅡ 숫자를 순서대로 배열에 반환해야 합니다. 문제는 위의 사이트에서 상세히 확인 가능합니다.

 

접근 아이디어

 

1. info 배열로 만들 수 있는 key 값을 모두 구해주도록 합니다. 단, key 값에는 '-'를 포함한 key도 만들어 주어야 합니다.

2 이진 탐색을 해야하기 때문에 key에 대한 ArrayList값들을 정렬해 주어야 합니다. 단, query 반복문안에서 하지 않도록 합니다. (key 값의 경우의 수는 4 x 3 x 3 x 3가지의 경우의 수만 존재하기 때문에 효율성 테스트에서 통과할 수 있습니다.

3. 이진 탐색을 통해서 결과값을 반환해야만 효율성 테스트에서 통과가 가능합니다.

 

조심해야할 점

 

1. query 배열의 최대 길이는 100,000이기 때문에 반복문 안에서 정렬하지 않도록 합니다.

2. 이진 탐색 적용시 부등호를 잘 사용하여야 합니다.

3. Kotlin 언어로 구현시 query문 내에서 scope function사용하니 효율성에서 시간 초과가 떴습니다.

 

- Java

import java.util.*;

class Solution {
    static Map<String, List<Integer>> map = new HashMap<>();

    public int[] solution(String[] info, String[] query) {
        int[] answer = new int[query.length];

        for(int i=0; i<info.length; i++) {
            dfs(0, "", info[i].split(" "));
        }

        Iterator<String> iterator = map.keySet().iterator();
        while(iterator.hasNext()) {
            String key = iterator.next();
            List<Integer> list = map.get(key);
            Collections.sort(list);
        }

        for(int i=0; i<query.length; i++) {
            String[] keyValue = query[i].replaceAll(" and ", "").split(" ");
            String key = keyValue[0];
            String value = keyValue[1];

            if(!map.containsKey(key)) {
                answer[i] = 0;
                continue;
            }

            answer[i] = bs(map.get(key), Integer.parseInt(value));
        }

        return answer;
    }

    public static void dfs(int depth, String key, String[] info) {
        if(depth == 4) {
            if(map.containsKey(key)) {
                map.get(key).add(Integer.parseInt(info[4]));
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(Integer.parseInt(info[4]));
                map.put(key, list);
            }
            return;
        }

        dfs(depth + 1, key + "-", info);
        dfs(depth + 1, key + info[depth], info);
    }

    public static int bs(List<Integer> list, int target) {
        int start = 0;
        int end = list.size() - 1;

        while(start <= end) {
            int mid = (start + end) / 2;
            if(list.get(mid) >= target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return list.size() - start;
    }
}

- Kotlin

class Solution {
    val map = HashMap<String, ArrayList<Int>>()

    fun solution(info: Array<String>, query: Array<String>): IntArray {
        var answer = IntArray(query.size)

        for (subInfo in info) {
            dfs(0, "", subInfo.split(" "))
        }

        val iterator = map.keys.iterator()
        while (iterator.hasNext()) {
            val key = iterator.next()
            val list = map[key] ?: ArrayList()
            list.sort()
        }

        for (index in query.indices) {
            val keyValue = query[index].replace(" and ".toRegex(), "").split(" ").toTypedArray()
            val key = keyValue[0]
            val value = keyValue[1]

            if (!map.containsKey(key)) {
                answer[index] = 0
                continue
            } else {
                answer[index] = bs(map[key]!!, value.toInt())
            }
            
            //아래 코드 사용시 효율성에서 탈락
            //answer[index] = map[key]?.let { bs(it.toList(), value.toInt()) } ?: 0
        }

        return answer
    }

    fun dfs(depth: Int, key: String, info: List<String>) {
        if (depth == 4) {
            if (map.containsKey(key)) {
                map[key]!!.add(info[4].toInt())
            } else {
                val list = ArrayList<Int>()
                list.add(info[4].toInt())
                map[key] = list
            }
            return
        }

        dfs(depth + 1, "${key}-", info)
        dfs(depth + 1, key + info[depth], info)
    }

    fun bs(list: List<Int>, target: Int): Int {
        var start = 0
        var end = list.size - 1

        while (start <= end) {
            val mid = (start + end) / 2
            if (list[mid] >= target) {
                end = mid - 1
            } else {
                start = mid + 1
            }
        }

        return list.size - start
    }
}

 

 

좌(Java 채점 결과), 우(Kotlin 채점 결과)