[Programmers] 순위 검색

🔒 문제

키 포인트

1. 쿼리에 조건에 대한 모든 결과를 미리 해시맵에 저장한다는 아이디어를 떠올릴 수 있는가?

2. 값을 score 로 두고, 모든 값에 대해 오름차순으로 정렬하고 이분탐색을 사용해서 조건을 만족하는 개수를 구할 수 있는가?

3. 중복이 허용된 배열에 대해 이분탐색으로 index 를 찾는 코드를 정확하게 작성할 수 있는가?

4. 늦어도 80분 내에 이 모든 것을 풀어낼 수 있는가?

사고 과정

🔑 Kotlin Code

class RankSearch {
    private fun binarySearch(arr: ArrayList<Int>, targetScore: Int) : Int {
        var startIdx: Int = 0
        var endIdx: Int = arr.lastIndex

        while (startIdx <= endIdx) {
            var mid = (startIdx + endIdx) / 2
            if(arr[mid] >= targetScore) startIdx = mid + 1
            if(arr[mid] < targetScore) endIdx = mid - 1
        }
        // Not found
        return endIdx
    }

    fun solution(records: Array<String>, queries: Array<String>): IntArray {
        // 1. HashMap 설정
        // Info 로 부터 HashMap 키를 쿼리 결과로 아예 캐싱해버림.
        // 쿼리 가능한 모든 condition 에 대한 해시 테이블을 만듦.
        // value 는 score list 로 여기서 갯수만 찾으면 됨.

        val answer = IntArray(queries.size){0}

        val hashMap = HashMap<String, ArrayList<Int>>()


        // 해시 테이블 생성 (쿼리 결과 캐싱 테이블)
        for (record in records) {
            var (language, jobSkill, career, soulFood, scoreString) = record.split(" ")
            val score = scoreString.toInt()

            // 모든 조건에 대해 만들어 줘야함..
            val languages = arrayOf(language, "-")
            val jobSkills = arrayOf(jobSkill, "-")
            val careers = arrayOf(career, "-")
            val soulFoods = arrayOf(soulFood, "-")

            for (lan in languages) {
                for (job in jobSkills) {
                    for (ca in careers) {
                        for (soulF in soulFoods) {
                            // if 로 키 존재 유무 때리기보다 어차피 추가할거 마찬가지니까 getOrDefault 하면 됨.
                            val key = "$lan $job $ca $soulF"
                            val scoreList = hashMap.getOrDefault(key, ArrayList<Int>())
                            scoreList.add(score)
                            hashMap[key] = scoreList
                        }
                    }
                }
            }

        }

        // 2. 모든 해시테이블의 점수는 내림차순 되있는 상태여야한다.
        for (scores in hashMap.values) {
            scores.sortDescending()
        }

        // 3. 이분탐색으로 갯수 빠르게 구하기
        queries.forEachIndexed { index, query ->
            var (language, jobSkill, career, soulFoodStr) = query.split(" and ")
            val soulFood = soulFoodStr.split(" ")[0]
            val conditionScore = soulFoodStr.split(" ")[1].toInt()

            val keyCondition = arrayOf(language, jobSkill, career, soulFood).joinToString(" ")


            // 이분 탐색
            if (!hashMap.containsKey(keyCondition)) answer[index] = 0
            else {
                val minScoreIndex = binarySearch(hashMap[keyCondition]!!, conditionScore)
                answer[index] = if (minScoreIndex >= 0) minScoreIndex + 1
                else 0
            }

            // 이분 탐색없이 이 방식을 사용하면 효율성 반토막.
//            if (!hashMap.containsKey(keyCondition)) answer[index] = 0
//            else {
//                val lastIndex = hashMap[keyCondition]!!.indexOfLast { it >= conditionScore }
//                answer[index] = if (lastIndex < 0) 0
//                else lastIndex +  1
//            }

        }

        // 쿼리에 대한 score 값 갯수를 이분 탐색으로 받아옴

        return answer

   }
}