[프로그래머스/Kotlin] 순위 검색 (Lv. 2)

문제

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

• 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
• 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
• 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
• 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

 

인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.

코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.

• 코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
• 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?

즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.

* [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?

 

 

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

 

제한사항

• info 배열의 크기는 1 이상 50,000 이하입니다.
• info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
  • 개발언어는 cpp, java, python 중 하나입니다.
  • 직군은 backend, frontend 중 하나입니다.
  • 경력은 junior, senior 중 하나입니다.
  • 소울푸드는 chicken, pizza 중 하나입니다.
  • 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
• query 배열의 크기는 1 이상 100,000 이하입니다.
• query의 각 문자열은 "[조건] X" 형식입니다.
  • [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
  • 언어는 cpp, java, python, - 중 하나입니다.
  • 직군은 backend, frontend, - 중 하나입니다.
  • 경력은 junior, senior, - 중 하나입니다.
  • 소울푸드는 chicken, pizza, - 중 하나입니다.
  • '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
  • X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
  • 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

 

입출력예

 

풀이 방법(시간 초과)

class Solution {
    fun solution(info: Array<String>, query: Array<String>): IntArray {
        var answer = IntArray(query.size, {0})
        for((index,q) in query.withIndex()){
            var company = q.split(" ").filter{ it != "and"}
            
            for(i in info){
                var mine = i.split(" ")
                
                if((company[0] == mine[0] || company[0] == "-") &&
                        (company[1] == mine[1] || company[1] == "-") &&
                        (company[2] == mine[2] || company[2] == "-") &&
                        (company[3] == mine[3] || company[3] == "-") &&
                        company[4].toInt() <= mine[4].toInt()){
                    answer[index]++
                }
            }
        }
        return answer
    }
}

query 배열을 반복하면서 " "를 기준으로 자르고 and가 아닌 문자열만 company 리스트에 넣었다.

그리고 info 배열을 반복하면서 같은 인덱스마다 각각 비교했다.

이렇게 풀었더니 정확성은 100%였지만 시간이 너무 오래 걸렸고 효율성에서 시간초과가 떴다.

그래서 그냥 구글링해서 다른 분 풀이를 봤는데 헉 했다 .. 카카오에서 올린 풀이였는데 진짜 신기한 풀이였다.

 

참고 풀이

일단 이 문제는 주어진 info 배열에서 나올 수 있는 경우의 수를 dfs로 map에 전부 더한다.

예를 들면 info에서 주어진 "java backend junior pizza 150"는 map에

----=[150]

java---=[150]

-backend--=[150]

--junior-=[150]

---pizza=[150]

javabackend--=[150]

java-junior-=[150]

java--pizza=[150]

-backendjunior-=[150]

-backend-pizza=[150]

--juniorpizza=[150]

javabackendjunior-=[150]

javabackend-pizza=[150]

java-juniorpizza=[150]

-backendjuniorpizza=[150]

javabackendjuniorpizza=[150] 와 같이 16가지로 저장될 수 있다.

만약 다음에  "java frontend - - 200"와 같이 주어졌다면 java---=[150] 는 java---=[150,200]로 변경된다.

 

1. info의 전체 경우의 수를 담을 map을 생성한다. key는 문자열을 담고, value에는 코딩테스트 점수의 리스트가 담긴다.

val map = HashMap<String, ArrayList<Int>>()

 

2. info를 반복하며 dfs를 실행한다.

info.map {
    dfs(0, "", it.split(" "))
}

 

3. 만약 깊이가 4가 아니라면 dfs를 돌린다.

깊이가 4가 된다면 map에 key, value를 저장한다.

만약 key가 존재한다면 value에 값을 추가하고, 존재하지 않다면 key, value를 추가한다.

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)
}

 

4. map의 value를 기준으로 정렬한다. 정렬하는 이유는 이분 탐색을 해야하기 때문이다.

map.values.map { it.sort() }

 

5. query를 반복하면서 " and " 는 불필요한 요소이기 때문에 ""으로 바꿔주고 공백을 기준으로 str에 담는다.

그럼 str = [javabackendjuniorpizza, 100]와 같이 담긴다.

그래서 만약 map에 str[0]이 없다면 0을 추가하고 있다면 이분 탐색을 실행한다.

query.mapIndexed { index, string->
    //[javabackendjuniorpizza, 100] 이런 식으로 담음
    val str = string.replace(" and ", "").split(" ")
    //만약 키가 없다면 0
    if (!map.containsKey(str[0])) {
        answer[index] = 0
        //있다면 이분탐색
    } else {
        answer[index] = binarySearch(map[str[0]]!!, str[1].toInt())
    }
}

 

6. high에는 점수가 담긴 배열의 마지막 인덱스 번호를 담고 while문을 돌리면서 점수를 만족하는 인덱스의 값을 구한다.

while문을 빠져나오면 low에 해당하는 인덱스 번호부터 리스트의 마지막 인덱스까지 모두 조건을 만족한다.

그래서 applicant.size - low를 한다.

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
}

 

 

7. binarySearch에서 return된 값을 answer 배열에 저장하고 리턴한다.

answer[index] = binarySearch(map[str[0]]!!, str[1].toInt())

return answer

 

참고 블로그

https://everyday-develop-myself.tistory.com/97

순위 검색 - Kotlin

좋은 코드 감사합니당 :)

 

코드

class Solution {
    val map = HashMap<String, ArrayList<Int>>()

    fun solution(info: Array<String>, query: Array<String>): IntArray {
        val answer = IntArray(query.size)

        //16 * 6 = 96가지
        info.map {
            dfs(0, "", it.split(" "))
        }
        //value를 기준으로 정렬
        map.values.map { it.sort() }
        
        query.mapIndexed { index, string->
            //[javabackendjuniorpizza, 100] 이런 식으로 담음
            val str = string.replace(" and ", "").split(" ")
            //만약 키가 없다면 0
            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
    }
}

 

 

 

 

 

코딩테스트 연습 - 순위 검색 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스