2021 카카오 코테 문제 - 순위 검색 풀이 [Kotlin]

2021 카카오 코드 테스트의 문제 3번인 순위 검색에 대한 풀이입니다.

아직 배울 것이 많아 코드에 부족함이 있을 수 있으니 변경할 수 있는 점이 있다면 조언 부탁드립니다.

 

문제에 대한 설명과 풀이는 kakao Tech에서 확인할 수 있으며, 이 포스트에서는 설명과 풀이를 이용하여 kotlin으로 해결하는 방법을 작성하겠습니다.

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

추가로 아래의 ezsw님의 Youtube를 참고하여 작성하였습니다.

ezsw

입력 값

• info:   "언어 직군 경력 소울 푸드 점수"로 규칙을 갖은 String 요소를 저장한 Array
• query: "언어 and 직군 and 경력 and 소울 푸드 점수" 규칙을 갖은 String 요소를 저장한 Array

각 입력값은 나눌 수 있는 기준이 뚜렷합니다.

info는 공백을 기준으로, query는 and와 공백을 기준으로 나눈다면 동일하게 정보를 나눌 수 있습니다.

이 로직대로 구현해봅시다.

Code

fun main() {
    val info = "java backend junior pizza 150"
    val query = "java and backend and junior and pizza 100"
    val infoRegex = " ".toRegex() //공백을 기준으로 분리하기 위한 정규식
    val queryRegex = "( and )| ( )".toRegex()//\0and\0 또는 \0를 기준으로 분리하기 위한 정규식
    
    val (infoSList, infoScore) = SplitInfo(info, infoRegex)
    val (querySList, queryScore) = SplitInfo(query, queryRegex)
}

fun SplitInfo(info:String, regex:Regex):Pair<List<String>, Int> {
    var infoList:List:<String> = info.split(regex)
    var score = infoList.get(4).toInt()
    return Pair(infoList.subList(0, 4), score)
}

입력값을 나누었습니다!

입력값을 사용하기 쉽게 나누었다면 이제 문제를 풀이하는데 필요한 기본 정보를 생성해야 합니다.

우선 문제의 목표를 떠올려보면 Query의 조건에 맞는 Info가 몇 가지 존재하는가입니다.

 

예시로 info "java backend junior pizza 150"가 있습니다. 

여기서 입력값 query Array에서 정확히 일치하는 값만 찾고 싶지만 query는 조건을 고려하지 않는 "-" 키워드가 존재합니다.

그렇다면 "java backend junior pizza 150"가 가질 수 있는 경우의 수는 얼마나 있을까요?

언어: java, - (2가지)

직군: backend, - (2가지)

경력: junior, - (2가지)

푸드: pizza, - (2가지)

즉 경우의 수는 2 * 2 * 2 * 2로 16가지가 존재합니다.

 

물론 입력값의 query에 위의 16가지의 경우가 모두 존재할지 모릅니다.

존재하는지 유추하는 로직을 작성할 수 있겠지만 복잡성이 높아지고 효율이 떨어질 것이라 생각했습니다.

첫 시도

"java backend junior pizza 150"를 기준으로 하고 설명하겠습니다. (이하 입력값)

먼저 입력값에 대한 16가지의 경우의 수를 모두 Map에 기록할 것입니다.

Map은 16가지의 경우의 수를 Key로 두고 ArrayList<Int> 구조를 갖은 Value에 score를 추가할 것입니다.

Map<String, ArrayList<Int> 형태입니다.

 

이럴 경우 Map의 key와 query가 일치하여 원하는 score 그룹을 얻을 수 있게 됩니다.

이때 query의 요소 중 "-"를 제거하여 문자열의 길이를 줄이는 형태의 구조로 구현했습니다.

이럴 경우 위에서 작성한 SplitInfo 로직 이전에 query의 값에 존재하는 "-"를 " "로 replace 해야 합니다.

문제는 이럴 경우 경우의 수를 생성하기 위한 DFS 과정이 시간 소모가 큰 편이라 효율성에서 통과되지 못했습니다.

물론 이 과정만 문제였던 것은 아니었지만... 아무튼 이 로직을 개선해야 했습니다.

참고한 영상에서..

ezsw님의 영상을 참고해보니 풀이 방법이 달랐습니다.

Map에서 문자열 검색을 통해 Score 그룹을 가져오는 저와 다르게 ScoreList라는 1차원 List를 만들어 각 index가 key가 되도록 하는 방식이었습니다.

 

우선 입력값의 각 요소인 언어, 직군, 경력, 소울푸드의 모든 종류를 Key값으로 사용한 Map에 저장하였습니다.

 

key	value
-	0
cpp	1
java	2
python	3
backend	1
frontend	2
junior	1
senior	2
chicken	1
pizza	2

이 구조를 이용하여 위에서 말한 scoreList에 index를 만들 것입니다.

scoreList는 MutableList<MutableList<Int>>타입 입니다.

 

scoreList의 index를 통해 query에 대한 모든 경우의 수를 표현하기 위해서는 0~(4*3*3*3) - 1의 범위를 갖게 됩니다.

즉 108개의 범위를 갖게 되는데 요소를 통해 표현하기 위해선 아래와 같습니다.

• 언어 (0~3) * 3 * 3 * 3 = 0, 27, 54, 81
• 직군 (0~2) * 3 * 3 = 0, 8, 18
• 경력 (0~2) * 3 = 0, 3, 6
• 음식 (0~2) = 0, 1, 2

query가 - - - - 일 경우 0 + 0 + 0 + 0 = 0의 index 값을 만들 것입니다.

query가 python and frontend and senior and pizza일 경우 81 + 18 + 6 + 2 = 107의 index 값을 만들 것입니다.

이렇게 index를 만들어 내는 공식이 완성되었습니다.

 

이젠 입력값 info에서 값을 꺼내 위의 공식을 통해 scoreList를 완성할 차례입니다.

계산해야 할 info의 값은 1개당 만들어 낼 수 있는 경우의 수가 총 16가지입니다.

이를 비트 연산을 통해 표현해봅시다.

0의 bit는 0000 | 1의 bit는 0001

...

15의 bit는 1111 입니다.

각 자리의 비트는 순서대로 언어, 직군, 경력, 음식을 나타내며 1로 활성화되었을 경우 위에서 계산한 값을 합해주면 index가 됩니다.

Code

fun solution(info:Array<String>, query:Array<String>):IntArray {
        var answer:IntArray = IntArray(query.size) { 0 }
        var wordMap:MutableMap<String, Int> = SettingWordMap()
        var scoreList:MutableList<MutableList<Int>> = MutableList<MutableList<Int>>(4*3*3*3) { mutableListOf() }
        val infoRegex = " ".toRegex()
        val queryRegex = "( and )|( )".toRegex()

        info.forEach {
            val (infoList, score) = SplitInfo(it, infoRegex)
            val arr:IntArray = intArrayOf(
                wordMap.get(infoList.get(0))!! * 3 * 3 * 3,
                wordMap.get(infoList.get(1))!! * 3 * 3,
                wordMap.get(infoList.get(2))!! * 3,
                wordMap.get(infoList.get(3))!!)
			
            //4bit 씩 왼쪽으로 이동하여 총 0~15의 범위를 갖습니다.
            for(i in  0 until (1 shl 4)) {
                var index:Int = 0
                //1번부터 4번까지의 bit가 활성화 되었는지 검사합니다.
                for(j in 0 until 4) {
                    if(i and (1 shl j) != 0) {
                        index += arr[j]
                    }
                }
                scoreList.get(index).add(score)
            }
        }
}

거의 끝났습니다!

위 과정을 통해 score를 각 경우의 수에 맞게 분리하게 되었습니다.

자 힘들게 score를 분리한 이유를 다시 한번 상기해봅시다.

이 문제의 목적은 query의 조건에 맞는 사람의 수를 계산하는 것입니다.

"java backend junior chicken 150" 일 경우 조건 일치와 150점 이상인 사람의 수를 계산하는 것입니다.

위의 과정을 통해 이미 각 조건에 일치하는 지원자들의 점수를 List 형식으로 저장했습니다.

 

즉 scoreList의 조건에 맞는 index에서 query가 제시한 점수와 동일하거나 높은 값의 개수만 제출하면 끝인 것입니다.

filter를 사용해볼까

info에서 각 조건에 맞게 점수는 분리하였습니다.

점수는 MutableList<Int> 타입이며 query의 점수와 동일하거나 높은 값을 가져오기 위해선 다음과 같습니다.

var answer:IntArray = IntArray(query.size) { 0 }
var scoreList:MutableList<MutableList<Int>> = new MutableList<MutableList<Int>>(4*3*3*3) { mutableListOf() }
...
queryIndex = 1
queryScore = 150
val size = scoreList.get(index).filter { it >= queryScore }.size
answer.set(i, answer.get(i) + size)

이렇게 작성하면 간단히 결과를 나타낼 수 있지만, scoreList의 점수가 많으면 많을수록 filter를 통해 비교해야 할 값이 많으며 이는 곧 효율성을 통과하지 못하는 문제를 발생시킵니다.

 

Sort, binarySearch, low bound

맨 위의 링크인 kakao Tech 풀이 해설이나, ezsw님의 영상에서 확인할 수 있듯이 sort, binary search, low bound 사용을 권장하고 있습니다.

 

만약 값이 [100, 110, 120, 130, 140, 150, 160] 이 존재하고 130 이상의 값의 개수를 구하고 싶다면 배열의 전체 크기와 130의 index의 차를 계산하면 될 것입니다. (즉 100 ~ 130까지의 범위의 값만 비교하면 될 것입니다.)

Sort

이를 위해 우선 Sort를 진행해봅시다.

scoreList.forEach {
    it.sort()
}

Binary Search

정렬이 진행되었다면 조건에 알맞은(또는 가장 가까운) 값의 위치를 찾아내기 위해 binarySearch 함수를 사용해봅시다.

var ret:Int = scoreList.get(index).binarySearch(queryScore)

binarySearch는 인자로 넘겨준 값의 index를 반환합니다.

만약 정확히 일치하는 값을 찾지 못했다면 인자와 가장 가까운 값을 검색하게 됩니다.

그 후 (검색을 진행한 횟수 + 1) * -1 값을 반환합니다. (커서 느낌과 비슷합니다.)

• [0, 1, 2, 3]에서 3을 찾을 경우 3이 존재하므로 검색 횟수와 관계없이 3의 index인 3을 반환합니다.
• [0, 1, 2, 3]에서 4를 찾을 경우 0, 1, 2, 3 총 4회 검색을 진행했으며 존재하지 않았으므로 -5를 반환합니다.
• [0, 1, 2, 4, 5]에서 3을 찾을 경우 2가 가장 우선적으로 가까우며 3회 검색을 진행했으므로 -4를 반환합니다.

결과가 양수라면 (배열의 크기) - 반환된 값이 조건에 맞는 값에 대한 개수입니다.

결과가 음수라면 (배열의 크기) - ((반환된 음수의 값 + 1) * -1)이 조건에 맞는 값에 대한 개수입니다.

 

자 이 특징을 이용해 아래의 경우의 수를 해결할 수 있습니다.

[100, 110, 120, 140, 150, 160]에서 queryScore 값 130을 검색한다면, 값이 존재하지 않고 가장 가까운 120을 검색하여 -4를 반환합니다.

6 - ((-4 + 1) * -1)를 통해 결과는 3이 나왔으며, 조건에 맞는 140,150,160의 수와 동일하게 계산되었습니다!

Low Bound

위의 Binary Search로 끝났다면 좋았겠지만 한 가지 문제가 존재합니다.

만약 scoreList의 값이 [150,150,150,150,150,150,150]에 queryScore가 150이라면 어떤 값이 반환되어야 할까요?

가장 첫 번째 값의 index가 반환되었다면 이런 고민을 할 필요가 없을 텐데 아쉽게도 몇이 반환될지 모릅니다.

이 때문에 최소 범위를 찾기 위해 Low Bound를 구현해야 합니다.

 

만약 예시에서 3이 반환되었다면?  scoreList의 index 3번 값을 기준으로 왼쪽의 값을 queryScore와 비교 검사합니다.

만약 조건이 일치한다면 index 3을 2로 변경시키고, 이 과정을 반복하면 예시의 결과인 index 0을 얻을 수 있습니다.

Code

var queryIndex = 0
var queryScore = 150
var slist = scoreList.get(index)
var ret:Int = slist.binarySearch(queryScore)

//ret이 음수라면 binarySearch 로직으로 끝납니다.
if(ret < 0) {
    ret = (ret + 1) * -1
} else {
    for(j in ret downTo 0) {
        if(slist.get(j) == queryScore) {
            ret = j
        } else {
            break
        }
    }
}
answer.set(queryIndex, answer.get(queryIndex) + (slist.size - ret))

전체 코드를 보자

긴 설명을 하나로 합친 코드는 아래와 같습니다.

전체 코드

fun solution(info:Array<String>, query:Array<String>):IntArray {
    var answer:IntArray = IntArray(query.size) { 0 }
    var wordMap:MutableMap<String, Int> = SettingWordMap()
    var scoreList:MutableList<MutableList<Int>> = MutableList<MutableList<Int>>(4*3*3*3) { mutableListOf() }
    val infoRegex = " ".toRegex()
    val queryRegex = "( and )|( )".toRegex()

    info.forEach {
        val (infoList, score) = SplitInfo(it, infoRegex)
        val arr:IntArray = intArrayOf(
            wordMap.get(infoList.get(0))!! * 3 * 3 * 3,
            wordMap.get(infoList.get(1))!! * 3 * 3,
            wordMap.get(infoList.get(2))!! * 3,
            wordMap.get(infoList.get(3))!!)

        for(i in  0 until (1 shl 4)) {
            var index:Int = 0
            for(j in 0 until 4) {
                if(i and (1 shl j) != 0) {
                    index += arr[j]
                }
            }
            scoreList.get(index).add(score)
        }
    }

    scoreList.forEach {
        it.sort()
    }

    for(i in query.indices) {
        val(queryInfo, score) = SplitInfo(query.get(i), queryRegex)
        val index:Int = 
            (wordMap.get(queryInfo.get(0))!! * 3 * 3 * 3 +
            wordMap.get(queryInfo.get(1))!! * 3 * 3 +
            wordMap.get(queryInfo.get(2))!! * 3 +
            wordMap.get(queryInfo.get(3))!!)
            
        var ret:Int = scoreList.get(index).binarySearch(score)
        if (ret < 0) {
            ret = (ret + 1) * -1
        } else if(ret > 0) {
            for(j in ret downTo 0) {
                if(scoreList.get(index).get(j) == score) {
                    ret = j
                } else {
                    break
                }
            }
        }
        answer.set(i, answer.get(i) + (scoreList.get(index).size - ret))
    }

    return answer
}

fun SettingWordMap():MutableMap<String, Int> {
    var wordMap:MutableMap<String, Int> = HashMap<String, Int>()
    wordMap.put("-",            0)
    wordMap.put("cpp",          1)
    wordMap.put("java",         2)
    wordMap.put("python",       3)
    wordMap.put("backend",      1)
    wordMap.put("frontend",     2)
    wordMap.put("junior",       1)
    wordMap.put("senior",       2)
    wordMap.put("chicken",      1)
    wordMap.put("pizza",        2)
    
    return wordMap
}

fun SplitInfo(info:String, regex:Regex):Pair<List<String>, Int> {
    var infoList:List<String> = info.split(regex)
    val score = infoList.get(4).toInt()
    return Pair(infoList.subList(0, 4), score)
}