level2-72412.md

프로그래머스

순위 검색

• 출처: 2021 KAKAO BLIND RECRUITMENT
• 난이도: Level 2
• 풀이 언어: Swift
• 문제 요약: 지원자 정보와 개발팀의 문의조건이 String 배열로 주어질 때, 문의조건에 해당하는 사람들의 숫자를 배열에 담아 반환

코드

func solution(_ info:[String], _ query:[String]) -> [Int] {
    var db = [String: [Int]]()

    for i in info {
        let infos = i.split(separator: " ").map { String($0) }
        for language in [infos[0], "-"] {
            for job in [infos[1], "-"] {
                for career in [infos[2], "-"] {
                    for food in [infos[3], "-"] {
                        let key = "\(language) \(job) \(career) \(food)"
                        db[key, default: []].append(Int(infos[4])!)
                    }
                }
            }
        }
    }

    for j in db {
        db[j.key] = j.value.sorted()
    }

    var result = [Int]()
    for q in query {
        let querys = q.split(separator: " ").map { String($0) }
        let key = "\(querys[0]) \(querys[2]) \(querys[4]) \(querys[6])"
        if let scores = db[key] {
            var start = 0
            var end = scores.count - 1
            while start <= end {
                let mid = (start + end) / 2
                if scores[mid] >= Int(querys[7])! {
                    end = mid - 1
                } else {
                    start = mid + 1
                }
            }
            result.append(scores.count - start)
        } else {
            result.append(0)
        }
    }
    return result
}

회고

• 어려워서 검색을 통해서 풀었다🥲
• 이 문제는 효율성 테스트가 존재하는 문제이다. info 배열의 크기는 최대 50,000, query 배열의 크기는 최대 100,000이기 때문에 최악의 경우 연산이 50억번 발생한다. 그러므로 O(n)보다 효율적인 O(logn)의 풀이법을 찾아야 한다.
  • 딕셔너리를 사용해 지원자들을 그룹별로 적절하게 미리 분류한다. 이때 같은 조건에 대해 복수의 지원자가 포함될 수 있으므로 딕셔너리는 [String: [Int]]와 같은 형태가 된다.
  • 미리 분류해둔 그룹에서 X점 이상 맞은 지원자를 셀 때, [Int] 배열을 순차적으로 돌며 값을 하나하나 비교한다면 여전히 효율성 테스트를 통과할 수 없다. 그렇기 때문에 [Int] 배열을 오름차순으로 정렬한 후 배열에서 X보다 크거나 같은 숫자가 처음 나타나는 위치를 lower bound로 찾는 이분 탐색을 이용해야 한다.