Programmers 순위 검색

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

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

2021 KAKAO BLIND RECRUITMENT 순위 검색

 

이거 풀때 너무 힘들어서,,, 작성한다

 

첫번째로 접근한 방법은 input인 info List를 객체로 변환해 저장하고, 죄다 비교하는 거였다.

당연히 효율성에서 빵점이 나왔다.

Kakao Tech에서 나온 해설을 열심히 보며 코드를 작성했다.

 

예시

    info 1 : "java backend junior pizza 150"

    info 2 : "java frontend senior pizza 200"

 

1. info 정보 찢기

만약 info1로 "java backend junior pizza 150" 이 들어왔다고 하면,

질문으로 "- backend junior pizza" 가 들어오거나 "java - junior pizza"가 들어와도 모두 해당이 된다.

그래서 "java backend junior pizza"로 query가 통과될 수 있는 모든 경우의 수를 만든다. (그게 16가지)

 

	언어	분야	경력	음식	점수
1	java	backend	junior	pizza	150
2	-	backend	junior	pizza	150
3	java	-	junior	pizza	150
4	java	backend	-	pizza	150
5	java	backend	junior	-	150
6	-	-	junior	pizza	150
7	-	backend	-	pizza	150
8	-	backend	junior	-	150
9	java	-	-	pizza	150
10	java	-	junior	-	150
11	java	backend	-	-	150
12	-	-	-	pizza	150
13	-	-	junior	-	150
14	-	backend	-	-	150
15	java	-	-	-	150
16	-	-	-	-	150

이렇게 한명의 지원자 정보에 대해 16가지로 나타낼 수 있다.

다음 지원자 정보인 "java frontend senior pizza 200"을 info2라고 한다면,

info2 또한 위 표처럼 16가지로 쪼개질 수 있다. 그 중 info1과 겹치는 경우는

 

언어	분야	경력	음식	점수
java	-	-	pizza	[150, 200]
-	-	-	pizza	[150, 200]
java	-	-	-	[150, 200]
-	-	-	-	[150, 200]

이렇게 4가지가 될 것이다.

만약 query로 "java - - pizza 170"이 들어온다면, 위의 표에서 점수에서 170이 넘는 지원자는 한명 뿐이니, 답은 1이 된다.

 

이제 언어, 분야, 경력, 음식을 합쳐서 Map의 key값으로 만들고, 점수 List를 value로 설정한다.

이렇게 하면 반을 왔다.

 

이대로 모두 순차적으로 점수를 탐색하면 효율성에서 0점을 맞는다.

Kakao Tech에선 이진 탐색(binary search)을 사용하기를 권한다.

우선 map의 각 value들을 정렬한 뒤, binary search를 이용해 탐색하면 답을 구할 수 있는데

 

Kotlin에서 제공하는 binarySearch 함수는 동일한 요소가 있는 경우 제일 최소 인덱스 반환을 보장하지 않는다고 하여

직접 구현했다.

 

fun recursive(map: MutableMap<String, MutableList<Int>>, strs: List<String>, checked: Array<Boolean>, index : Int, depth: Int, max_depth: Int) {
    if(depth == max_depth) {
        // check된곳 "-"로 치환
        var str = StringBuilder()

        (0 until 4).forEach { j ->
            if (checked[j]) {
                str.append("-")
            } else {
                str.append(strs[j])
            }
        }

        val key = str.toString()
        val score = strs[4].toInt()
        if(map.containsKey(key)) {
            map[key]!!.add(score)
        }else {
            map[key] = mutableListOf(score)
        }
    }

    for(i in index until 4) {
        checked[i] = true
        recursive(map, strs, checked, i+1,depth+1, max_depth)
        checked[i] = false
    }
}

fun binarySearch(list: MutableList<Int>, target: Int):Int {
    var start = 0
    var end = list.size
    var mid: Int
    while (end - start > 0) {
        mid = (start + end) / 2
        if(target <= list[mid]) {
            end = mid
        }
        else {
            start = mid + 1
        }
    }

    return end
}

class Solution {
    fun solution(info: Array<String>, query: Array<String>): IntArray {
        var answerList = mutableListOf<Int>()
        var info_map = mutableMapOf<String, MutableList<Int>>()

        for (i in info) {
            val splitInfo = i.split(" ")

            for(j in 0..4){
                recursive(info_map, splitInfo, Array(4) {false}, 0,0, j)
            }
        }

        for(k in info_map.keys) {
            info_map[k]!!.sort()
        }

        for(q in query) {
            val str = q.replace("and ", "").split(" ")
            val key = str[0] + str[1] + str[2] + str[3]

            when(val scoreList = info_map[key]) {
                null -> answerList.add(0)
                else -> answerList.add(scoreList.size - binarySearch(scoreList, str[4].toInt()))
            }
        }
        return answerList.toIntArray()
    }
}

 

끗