[카카오] 순위 검색

• 2021 KAKAO BLIND RECRUITMENT
• 순위 검색
• Level 2

 

문제

각 항목에 대해 하나 씩 선택해야 함

• 개발 언어 항목 cpp, java, python
• 지원 직군 항목 backend, frontend
• 지원 경력구분 항목 junior, senior
• 선호 소울 푸드 chicken, pizza

 

• 지원자 정보 info

→ 배열 크기는 1 이상 50,000 이하

→  “개발언어 직군 경력 소울푸드 점수” 형식

→ 이 때 점수는 1 이상 100,000 이하

→ 스페이스 하나로 구분

[“java backend junior pizza 150”,

 ”python frontend senior chicken 210”]

 

• 요구 사항 query

→ 배열 크기는 1 이상 100,000 이하

→ “개발언어 and 직군 and 경력 and 소울푸드 점수” 형식

→ 특정 조건을 고려하지 않는 경우 - 로 표기

→ 점수는 해당 점수 이상 받은 사람을 구하면 됨

[“java and backend and junior and pizza 100”,

 ”cpp and - and senior and pizza 250”,

 ”- and backend and senior and - 150”,

 ”- and - and - and chicken 100”,

 ”- and - and - and - 150”]

 

각 요구사항에 대해 해당하는 지원자가 몇명인지 반환

예. [1,1,1,1,2,4]

 

Idea

1. 지원자 정보를 항목별로 배열로 만들고, 쿼리도 항목별로 쪼개서 각 쿼리별로 지원자를 매번 탐색하여 갯수를 셈 -> 시간 초과
2. 효율성을 통과하기 위한 방법

• 어떤 쿼리가 오더라도 해당 지원자 정보에 바로 접근할 수 있도록 모든 경우의 수를 갖는 딕셔너리를 만들기. 동일한 키에 대해서 여러 점수가 있을 수 있음

예. “java backend junior pizza 150”

→ “javabackendjuniorpizza”: [150]

→ “-backendjuniorpizza”: [150]

→ "-backend-pizza”: [150]

등등… 이러한 조합을 만들게 되면 하나의 지원자 정보에 대해서 16개의 조합이 나옴

• 각 키 값에 대한 점수 배열을 정렬해두기
• 각 쿼리에 해당하는 점수를 받아온 다음 해당 쿼리에서 요구하는 점수 이상의 값들이 몇 개인지 찾기

→ 이 때 그냥 검색하면 안되고, 이분 탐색(여기서는 lowerbound) 를 사용해야 함

 

Code

Swift

• 카카오 공식 해설이랑,, 여러 분들의 설명의 도움으로 효율성까지 통과한 코드..휴
• 여기서 중요한 포인트

1. 각 info 에 대해서 모든 16가지의 경우를 키로 만들어 말 그대로 - 에 대비하기,, (조합을 정말 이렇게 만들어야 하는 것인가..)
2. 딕셔너리를 만들었을 때 각 키에 대해서 저장된 모든 값을 정렬해둬야 함 (아주 중요)
3. 정렬된 점수 리스트에서 쿼리에서 요구하는 특정 점수 이상인 값의 개수를 찾기 위해 lowerBound 를 사용해야 함

• 사실 처음에 설명을 보고 1번과 3번은 했는데 그럼에도 통과가 안되는 것이다.. 모든 값을 무조건 정렬하는 것보다 3번을 하기 전에 당장 쓸 값에 대해서만 정렬하는게 낫지 않을까 하는 생각이었는데 아무튼 절대 통과가 안 된다
• 따라서 통과를 위해서는 2번 과정이 필수적이다

참고.
Swift 2021 KAKAO BLIND RECRUITMENT 순위 검색
Swift Algorithm 72412 순위 검색 (2021 카카오 블라인드 공채)

import Foundation

func solution(_ info:[String], _ query:[String]) -> [Int] {
    
    var infoDic: [String:[Int]] = [:]
    info.forEach {
        let infoArr = $0.components(separatedBy: " ")
        for lang in [infoArr[0], "-"] {
            for job in [infoArr[1], "-"] {
                for career in [infoArr[2], "-"] {
                    for food in [infoArr[3], "-"] {
                        let key = "\(lang)\(job)\(career)\(food)"
                        let value = infoDic[key] ?? []
                        infoDic[key] = value + [Int(infoArr[4])!]
                    }
                }
            }
        }
    }
    
    for item in infoDic {
        infoDic[item.key] = item.value.sorted() 
    }
    
    var result: [Int] = []
    query.forEach {
        let q = $0.components(separatedBy: " ").filter { $0 != "and" }
        let key = q[0...3].joined(separator: "")
        let score = Int(q[4])!
        
        if let value = infoDic[key] {
            let index = lowerBound(value, score)
            result.append(value.count - index)
        } else {
            result.append(0)
        }
    }
    
    return result
}

func lowerBound(_ scores: [Int], _ std: Int) -> Int {

    var left = 0
    var right = scores.count

    while left < right {
        let mid = (left + right) / 2
        if scores[mid] < std {
            left =  mid + 1
        } else {
            right = mid
        }
    }
    
    return right
}

 

• 이것은 16가지 조합을 만들 때 재귀를 사용하는 방법
• 다른 부분은 동일함
• 시간은 위의 코드보다 이렇게 한 경우가 더 빨랐음!

참고. Swift - 프로그래머스 순위 검색 

var infoDic: [String:[Int]] = [:]
func combination(_ arr: [String], _ cur: Int, _ score: Int) {
    if cur == arr.count {
        let key = arr.joined(separator: "")
        let value = infoDic[key] ?? []
        infoDic[key] = value + [score]
    } else {
        var next = arr
        combination(next, cur + 1, score)
        next[cur] = "-"
        combination(next, cur + 1, score)
    }
}

info.forEach {
    var infoArr = $0.components(separatedBy: " ")
    let score = Int(infoArr[4])!
    infoArr.removeLast()
    combination(infoArr, 0, score)
}

 

효율성 통과하지 못하는 코드

• 처음 푼 코드. 효율성에서는 시간 초과 뜸
• 어찌됐던 각 쿼리마다 filter 작업을 통해 이중 반복을 하는 것과 유사하기 때문

import Foundation

func solution(_ info:[String], _ query:[String]) -> [Int] {
    
    var infoArray: [[String]] = []
    info.forEach {
        infoArray.append($0.components(separatedBy: " "))
    }
    
    var result: [Int] = []
    query.forEach {
        let q = $0.components(separatedBy: " ").filter { $0 != "and" }
        
        let count = infoArray.filter {
            if q[0] != "-" && q[0] != $0[0] { return false }
            if q[1] != "-" && q[1] != $0[1] { return false }
            if q[2] != "-" && q[2] != $0[2] { return false }
            if q[3] != "-" && q[3] != $0[3] { return false }
            if Int(q[4])! > Int($0[4])! { return false }
            return true
        }.count
        result.append(count)
    }
    
    return result
}