[Level 2 / 이진탐색] 순위 검색 + Swift

순위 검색 문제

https://programmers.co.kr/learn/courses/30/lessons/72412?language=swift

풀이

주어진 info와 query를 이중 배열로 만들었다. 그리고 조건을 충족하는지를 알려주는 함수를 만들었다. 그러나 효율성 테스트에서 시간 초과가 떴다😫

func solution(_ info:[String], _ query:[String]) -> [Int] {
    let infoArr = info.map({ $0.components(separatedBy: " ") })
    let queryArr = query.map({ $0.components(separatedBy: " ").filter({ $0 != "and" }) })
    
    var result: [Int] = []
    
    func isMeetConditions(_ infoItem: [String], _ queryItem: [String]) -> Bool {
        for index in 0..<5 {
            if queryItem[index] == "-" { continue }
            if index < 4 {
                if infoItem[index] != queryItem[index]  { return false }
            } else {
                if Int(infoItem[index])! < Int(queryItem[index])! { return false }
            }
         }
        return true
    }
    
    for queryItem in queryArr {
        let infoItem = infoArr.filter({ isMeetConditions($0, queryItem) })
        result.append(infoItem.count)
    }
    
    return result
}

다시 풀이

아래의 사이트를 참고하였다. db를 만든 후 이진탐색으로 result를 얻는 방식이다. 예를 들어 info에서 "java backend junior pizza 150"인 경우, db의 key에는 "java backend junior pizza", "java junior pizza", "java backend pizza", "java backend junior ", "java pizza"... " _ _ "를 넣고 value에는 배열에 점수들을 넣는 방식으로 만든다. 그 후 점수 배열들을 정렬한 후(이진탐색을 위함) 이진탐색으로 조건을 충족하는 사람들의 수를 얻는다.

func solution(_ info:[String], _ query:[String]) -> [Int] {
    var db: [String: [Int]] = [:]
    var result: [Int] = []
    
    for data in info {
        let infoArr = data.components(separatedBy: " ")
        let langs = [infoArr[0], "-"]
        let jobs = [infoArr[1], "-"]
        let careers = [infoArr[2], "-"]
        let foods = [infoArr[3], "-"]
        let score = Int(infoArr[4])!
        
        for lang in langs {
            for job in jobs {
                for career in careers {
                    for food in foods {
                        let key = "\(lang) \(job) \(career) \(food)"
                        if db.keys.contains(key) {
                            db[key]?.append(score)
                        } else {
                            db[key] = [score]
                        }
                    }
                }
            }
        }
    }
    
    for data in db {
        let sortedData = data.value.sorted()
        db[data.key] = sortedData
    }

    query.forEach {
        let separatedQuery = $0.components(separatedBy: " ")
        
        let lang = separatedQuery[0]
        let job = separatedQuery[2]
        let career = separatedQuery[4]
        let food = separatedQuery[6]
        let score = Int(separatedQuery[7])!
        
        let key = "\(lang) \(job) \(career) \(food)"
        
        if let dbScores = db[key] {
            var start = 0
            var end = dbScores.count
            while start < end {
                let mid = (start + end) / 2
                if dbScores[mid] >= score {
                    end = mid
                } else {
                    start = mid + 1
                }
            }
            result.append(dbScores.count - start)
        } else {
            result.append(0)
        }
    }
    
    return result
}

참고사이트

https://nsios.tistory.com/128