2021 카카오 코드 테스트의 문제 3번인 순위 검색에 대한 풀이입니다.
아직 배울 것이 많아 코드에 부족함이 있을 수 있으니 변경할 수 있는 점이 있다면 조언 부탁드립니다.
문제에 대한 설명과 풀이는 kakao Tech에서 확인할 수 있으며, 이 포스트에서는 설명과 풀이를 이용하여 kotlin으로 해결하는 방법을 작성하겠습니다.
추가로 아래의 ezsw님의 Youtube를 참고하여 작성하였습니다.
입력 값
- 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)
}
'코테' 카테고리의 다른 글
2021 카카오 코테 문제 - 광고삽입 [Kotlin] (1) | 2021.05.26 |
---|