프로그래머스[programmers] - 순위검색(Kotlin)[LV2]

문제

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

프로그래머스

 

문제 풀이

개인적으로 풀었던 LV3 문제보다 어려웠다.

정확성과 효율성을 모두 검사하는 문제인데, 효율성을 통과하는 과정이 정말 어려웠다.

실제로 효율성을 통과하는 방법을 몰라서 구글링을 했다.

아마도 쿼리에 해당되는 사람을 찾는 과정에서 배열의 전체를 탐색하기에 시간이 초과된다고 예상은 했지만, 그 해결방안으로 이분탐색을 사용할 줄은 상상도 못 했다.. 정말 대단한 사람들이다.

 

그 외적으로는 주어진 Info에 대해서 만들어질 수 있는 모든 정보 조합을 생성한다.

예를 들어 A,B,C,D에 대한 조합을 생성할 때,

이런 식으로 8개의 조합이 만들어지고, 각각을 적용해보면 32개의 조합이 나올수가 있다. 점수는 무시해서는 안되는 정보이기에, -를 생략한 실제 점수값이 들어가게 될 것이다.

이런식으로 모든 정보와 그에 대응되는 점수값들을 HashMap 형태로 저장한다.

여기서 key는 java, backend, junior, pizza와 같은 정보들이고, value는 key에 해당되는 점수들이다.

이러면 우리는 info에 대응되는 모든 조합과 점수들을 알고 있다.

이렇게 얻은 정보를 바탕으로 쿼리문의 정보와 매칭을 하는 것이다.

쿼리문의 정보와 key를 비교해서, key가 있다면, 해당 쿼리에서 탐색하고자 하는 점수이상인 점수들의 크기를 리턴해주면 된다.

여기서 탐색을 하는 과정에서 이분탐색을 쓰지 않으면 시간초과가 발생한다.

아마 점수집합의 크기가 매우 커서 점수를 하나하나 비교하는 것보단 탐색만을 최적화하는 이분탐색을 사용하는 것이 시간을 줄일 수 있다.

우리는 점수를 찾는 것이 아닌, 쿼리문에 점수 이상인 점수들의 개수를 찾는 것이기 때문에 이분탐색을 사용해서, 시간을 줄일 수 있다.

이번 문제는 배열에서 탐색의 시간을 줄이기 위한 방안으로 이분탐색을 떠올리지 풀수 없는 문제이다.

이분탐색을 사용하지 않더라도, 배열의 탐색을 줄이기 위한 다른방법을 사용해도 상관없지만, 가장 대중적인 방법인 이분탐색을 사용하는 분들이 많았고, 나도 그에 따라서 이분탐색으로 문제를 해결했다.

전체 코드

import java.util.*

class Solution {

    data class Info(val language: String, val position: String, val career: String, val food: String)

    val infoMap = HashMap<Info, ArrayList<Int>>()
    fun solution(info: Array<String>, query: Array<String>): IntArray {
        var answer: IntArray = intArrayOf()
        for (information in info) {
            val info = information.split(" ")
            val list = mutableListOf<String>()
            makeInformation(info, list, 0)
        }
        for (map in infoMap) {
            map.value.sort()
        }
        answer = matchQuery(query)
        return answer
    }

    fun makeInformation(infos: List<String>, list: MutableList<String>, depth: Int) {
        if (depth == 4) {
            val info = Info(list[0], list[1], list[2], list[3])
            if (infoMap.contains(info)) {
                infoMap[info]!!.add(infos[4].toInt())
            } else {
                val list = ArrayList<Int>()
                list.add(infos[4].toInt())
                infoMap.put(info, list)
            }
            return
        }
        list.add("-")
        makeInformation(infos, list, depth + 1)
        list.removeLast()
        list.add(infos[depth])
        makeInformation(infos, list, depth + 1)
        list.removeLast()

    }

    fun matchQuery(querys: Array<String>): IntArray {
        val result = IntArray(querys.size) { 0 }
        for (i in 0 until querys.size) {
            val q = querys[i].replace(" and ", " ")
            val query = q.split(" ")
            val info = Info(query[0], query[1], query[2], query[3])
            result[i] = findUser(info, query[4].toInt())
        }
        return result
    }

    fun findUser(info: Info, score: Int): Int {

        if (infoMap.contains(info)) { //키가 잇을 경우
            val list = infoMap.get(info)
            if (list == null)
                return 0
            return binary(list, score)
        } else
            return 0
    }

    fun binary(list: ArrayList<Int>, score: Int): Int {
        var start = 0
        var end = list.size - 1

        while (start <= end) {
            var mid = (start + end) / 2
            if (list.get(mid) < score)
                start = mid + 1
            else
                end = mid - 1
        }
        return list.size - start
    }
}