[프로그래머스] 2021 KAKAO BLIND RECRUITMENT 순위 검색 with Kotlin

문제

Info에는 4가지 항목과 코딩테스트 점수

• 개발 언어 (cpp, java, python, -)
• 지원 직군 (backend, frontend, -)
• 경력 (junior, senior, -)
• 소울 푸드 (chicken, pizza, -)
• 점수

query에는 개발팀에서 궁금해하는 조건이 다음과 같이 주어진다.

• "java and backend and junior and pizza 100"
• '-' 는 해당 조건을 고려하지 않는다.

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

풀이 과정

저도 풀다가 몰라서 다른 블로그를 참고했습니다...

그냥 for문으로 풀었을 경우에는 정확성은 통과되지만 효율성에서 떨어지게 된다.

 

1. info의 4가지 항목을 바탕으로 나올수 있는 모든 조합을 map에 key로 저장한다.

2. value는 코딩테스트 점수를 List로 저장

3. value를 기준으로 map 정렬

4. query의 코테 점수를 기준으로 이진탐색으로 조건에 맞는 사람들의 숫자 찾기

 

코드

class Solution {
    val map = HashMap<String, ArrayList<Int>>()
    
    fun solution(info: Array<String>, query: Array<String>): IntArray {
        var answer: IntArray = IntArray(query.size, {0})
        
        //가능한 모든 조합 저장
        info.map {
            dfs(0, "", it.split(" "))
        }
        
        //정렬
        map.values.map { it.sort() }
        
        // 탐색
        query.mapIndexed { index, string->
            val str = string.replace(" and ", "").split(" ")
            
            if (!map.containsKey(str[0])) {
                answer[index] = 0
            } else {
                answer[index] = binarySearch(map[str[0]]!!, str[1].toInt())
            }
        }
        
        return answer
    }
    
    // 가능한 조합 생성
    fun dfs(depth: Int, key: String, info: List<String>) {
        if (depth == 4) {
            if (map.containsKey(key)) {
                map[key]!!.add(info[4].toInt())
            } else
                map[key] = arrayListOf(info[4].toInt())
            return
        }
        dfs(depth + 1, "$key-", info)
        dfs(depth + 1, key + info[depth], info)
    }
    
    // 이진 탐색
    fun binarySearch(applicant: List<Int>, target: Int): Int {
        var low = 0
        var high = applicant.lastIndex
        
        while (low <= high) {
            val mid = (low + high) / 2

            if (applicant[mid] >= target)
                high = mid - 1
            else
                low = mid + 1
        }
        return applicant.size - low
    }
}