문제 링크

문제 풀이 아이디어

시간복잡도

info의 길이가 최대 50,000 그리고 query의 길이가 최대 100,000입니다. 따라서 각각 N과 M이라고 하겠습니다. 일단 M이 굉장히 크므로 딱 1번만 순회해야 합니다. 그리고 N의 길이도 작지 않습니다. O(N^2)를 하면 시간초과가 날 가능성이 큽니다.

일단 가장 쉽게 생각할 수 있는 것이 개발자들을 query마다 모두 완전탐색하면서 구현하는 방법입니다. 간단하게 O(NM)인데요. 아마 무조건 시간초과가 나는 크기입니다.

M을 줄이는 것은 불가능

M(query의 길이)는 어떻게 손 쓸 방법이 없습니다. 무조건 1번은 순회해야 합니다. 그렇다면 N을 최대한 줄여야 합니다. 즉 개발자들을 완전탐색 하지 않고 다른 탐색 방법을 사용해야 한다는 것입니다.

dictionary 사용

일단 첫번째로 query마다 개발자들을 분리해서 dict에 저장하는 방법입니다. dict를 [String:[Int]]의 형태로 만들어서 각각의 key를 query의 포맷과 일치하게 하면 됩니다.

예를 들어 “java backend junior pizza”의 개발자라면 “- - - -”, “java - - -”, “- backend - - “ 등의 키에 모두 점수를 append하는 방식입니다.

이렇게 하면 query할 때마다 개발자들을 완전탐색하지 않고 query와 일치하는 key를 가진 개발자들만 탐색하면 됩니다.

binary search 사용

score를 가려내는 과정도 완전탐색을 사용하지 않고 정렬을 한 후에 이진탐색을 사용하면 됩니다. 이진탐색은 O(logN)의 시간복잡도를 가지므로 훨씬 속도를 올릴 수 있습니다.

시간복잡도 계산

dict를 만들 때 O(N)입니다. 그리고 각각의 dict[key]를 정렬할 때 O(NlogN)입니다. 그리고 각각 query에 따라서 이진탐색을 하므로 O(MLogN)입니다. 최종적으로 O(N + NlogN + MlogN)인데요. 최고차항만 남기면 O(MlogN)입니다. log50000은 15 정도이므로 시간초과를 걱정할 필요는 없습니다.

코드

// 각각의 개발자의 특성으로 key를 만드는 함수
func makeKeys(dev: [String]) -> [String] {
    var result = [String]()
    
    // 각각의 특성마다 dev의 특성 혹은 "-"(관계없음)을 조합하여 key를 만든다 -> dfs
    func combi(_ now: [String]) {
        if now.count == 4 {
            result.append(now.joined())
            return
        }
        
        let index = now.count
        
        combi(now + [dev[index]])
        combi(now + ["-"])
    }
    
    combi([])
    
    return result
}

// binary Search를 통해서 score이상의 사람들이 몇명인지 찾는 함수
func binarySearch(_ scores: [Int], _ score: Int) -> Int {
    // 목표: scores[s]가 score보다 크거나 같은 수 중에 가장 작은 수를 찾는 것
    var s = 0, e = scores.count
    
    while s != e {
        // 현재 영역의 중간이 score보다 큰 경우
        if scores[(s + e) / 2] >= score {
            e = (s + e) / 2 // 더 낮은 점수대 검색
        } else {
            s = (s + e) / 2 + 1 // 더 높은 점수대 검색
        }
    }
    
    if s < scores.count {
        return scores.count - s
    } else { // s == scores.count인 경우: 모든 사람은 점수가 score보다 낮은 경우
        return 0
    }
    
}

func solution(_ info:[String], _ query:[String]) -> [Int] {
    
    var dict = [String:[Int]]()
    let info = info.map { $0.split(separator: " ").map { String($0) } }
    
    // dev를 key들로 바꾸고 각각의 value에 dev의 점수를 append
    for dev in info {
        let keys = makeKeys(dev: dev), score = Int(dev[4])!
        for key in keys {
            dict[key, default: []].append(score)
        }
    }
    
    // 이진 검색을 위한 value 정렬
    for key in dict.keys {
        dict[key]!.sort()
    }
    
    let queries = query.map { $0.split(separator: " ").map { String($0) }.filter { $0 != "and" } }
    
    var ans = [Int]()
    for query in queries {
        let key = Array(query[0..<4]).joined() // query를 key로
        let score = Int(query[4])!
        guard let scores = dict[key] else {
            ans.append(0)
            continue
        }
        ans.append(binarySearch(scores, score)) // 이진검색을 통해서 갯수 세기
    }
    
    return ans
}