순위 검색 (Lv.2)

문제 링크

풀이

import Foundation

func solution(_ info:[String], _ query:[String]) -> [Int] {
    var infoArr = info.map { Man($0) }
    infoArr.sort(by: { $0.score < $1.score })
    var dic: [String: [Int]] = [:] // 모든 경우의 수에 대한 해시테이블
    
    let queryArr = query.map { str -> Query in
                              var strArr = str.components(separatedBy: " and ")
                              let tempArr = strArr.removeLast().components(separatedBy: " ")
                              let score = Int(tempArr[1])!
                              strArr.append(tempArr[0])
                              let query = strArr.reduce("") { $0 + $1 }
                              
                              if dic[query] == nil {    // 해당 키에 값이 없었다면 입력한다.
                                  updateDic(query, strArr, infoArr, &dic)
                              }
                              
                              return Query(query: query, score: score)
    }
    
    var result: [Int] = []
    for query in queryArr {
        let filtered = dic[query.query]!
        let score = query.score
        // 이진탐색
        var high = filtered.count - 1
        var low = 0
        while high >= low {
            let middle = (low + high) / 2

            if filtered[middle] >= score {
                high = middle - 1
            } else {
                low = middle + 1
            }
        }
        
        result.append(filtered.count - low)
    }
    
    return result
}

func updateDic(_ query: String, _ queryArr: [String], _ mans: [Man], _ dic: inout [String: [Int]]) {
    var filtered = mans
        
    let lang = queryArr[0]
    if lang != "-" {
        let langEnum = Lang(rawValue: lang)!
        filtered = filtered.filter { $0.lang == langEnum }
    }

    let part = queryArr[1]
    if part != "-" {
        let bool = part.hasPrefix("f")
        filtered = filtered.filter { $0.isFront == bool }
    }

    let age = queryArr[2]
    if age != "-" {
        let bool = age.hasPrefix("j")
        filtered = filtered.filter { $0.isJunior == bool }
    }

    let food = queryArr[3]
    if food != "-" {
        let bool = food.hasPrefix("p")
        filtered = filtered.filter { $0.isPizza == bool }
    }

    dic[query] = filtered.map { $0.score }
}

struct Man {
    let lang: Lang
    let isFront: Bool
    let isJunior: Bool
    let isPizza: Bool 
    let score: Int 
    
    init(_ str: String) {
        let arr = str.components(separatedBy: " ")
        self.lang = Lang(rawValue: arr[0])!
        self.isFront = arr[1].hasPrefix("f")
        self.isJunior = arr[2].hasPrefix("j")
        self.isPizza = arr[3].hasPrefix("p")
        self.score = Int(arr[4])!
    }
}

struct Query {
    let query: String
    let score: Int
}

enum Lang: String {
    case cpp = "cpp"
    case java = "java"
    case python  = "python"
}

후기

처음 지문을 읽었을 때 너무나도 쉽지 않나? 생각들었던 문제.
그저 파싱하고 값뽑아내서 나열하면 그만인 문제 아닌가? 라는 가벼운 생각이 들었지만 오만이었다.
정확성 테스트는 다 통과했지만 효율성 테스트에서 전부다 탈락.

이걸 어떻게 효율성을 높일 수 있을까 고민했고
첫번째로는 점수를 오름차순으로 정렬하고 이진탐색으로 찾으려는 점수 이상구간을 빠르게 찾게하였다.
그래도 효율성 테스트 탈락...

두번째로는 해시테이블(딕셔너리)로 찾으려는 구간을 전부 맵핑 시켜 복잡도를 O(N)으로 맞추게하였다.
효율성 전부 성공!

해시테이블이 빠르긴 빠르구나하는걸 새삼알게된 문제.