[프로그래머스] 순위 검색 Swift

문제 풀이

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

본 문제는 정확성 테스트와 효율성 테스트 두 가지 방식으로 검증하는 문제입니다. 효율성 테스트의 경우 주어진 시간 내에 실행이 완료되어야 하므로, 최적화된 구현 방법을 고민할 필요가 있습니다.

우선, 매 문의 조건마다 INFO 배열에서 조건에 해당하는 지원자들을 찾으면서 X점 이상 받은 사람은 몇 명인지 구한다면 정확성 테스트를 통과할 수 있습니다.
그러나 효율성 테스트의 경우에는 위와 같은 방식으로 매번 지원자들을 찾는다면 통과할 수 없습니다. 문제 해결을 위해서, 지원자들을 그룹별로 적절하게 미리 분류해두면 매 문의 조건마다 지원자들을 INFO 배열에서 찾지 않아도 됩니다.

예를 들어, “java backend junior pizza 150” 지원자의 경우 다음과 같이 16가지 그룹에 속하게 됩니다.

검색 조건이 “java and backend and junior and pizza 100″이라 하면, 위 지원자는 검색 대상에 포함되며, 검색 조건이 “java and – and junior and – 100” 인 경우에도 검색 대상에 포함이 됩니다.

따라서 모든 지원자들을 위와 같은 방식으로 분류한 후 같은 그룹의 지원자끼리 묶어두고, 해당 그룹에서 점수를 기준으로 오름차순 정렬해 둡니다.

이제, 검색 조건이 주어질 경우 INFO 배열에서 지원자들을 찾지 않고, 미리 분류해둔 그룹에서 X점 이상 맞은 지원자 수를 세주기만 하면 됩니다.

이때, X점 이상 맞은 지원자를 찾기 위해 해당 그룹의 최저점, 혹은 최고점부터 순차적으로 검색한다면 여전히 오랜 시간이 걸리게 됩니다. 이때, 숫자가 오름차순으로 정렬된 배열에서 X라는 숫자를 찾는 효율적인 방법으로 binary search를 사용할 수 있습니다. 이때, 배열에 X가 없을 수도 있으므로, 배열에서 X보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 하며, 이는 lower bound를 이용하면 됩니다.

1. info각각의 DB를 생성해준다.
   • DB는 Dictionary [String: [Int]] = (key : 점수를 뺀 info, value(해당 쿼리에 속하는 점수들))로 생성해준다.
   • key는 "-"를 포함한 값 까지 생성해준다. ( 위 이미지 참조 )
2. query에서 key를 추출하여 value와 query의 점수를 비교해준다.
   • 많은 정보의 비교를 위해 선형 검색(O(n)) 보다 빠른 이진 검색(O(log n))을 사용한다.

나의 풀이

• 1차 시도 (효율성 실패)

for i in 0..<queryCnt {
    let arr1 = query[i].components(separatedBy: " ")
    result.append(0)
    for j in info{
        if j.contains(arr1[0]) || arr1[0] == "-"{
            if j.contains(arr1[2]) || arr1[2] == "-"{
                if j.contains(arr1[4]) || arr1[4] == "-"{
                    if j.contains(arr1[6]) || arr1[6] == "-"{
                        let arr2 = j.components(separatedBy: " ")
                        if (Int(arr2[4]) ?? 0 >= Int(arr1[7]) ?? 0) || arr1[7] == "-"{
                            result[i] += 1
                        }
                    }
                }
            }
        }
    }
}

• 2차 시도 ( 참고 사이트 )

import Foundation

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

    // db 생성
    for i in info {
        let arr = i.components(separatedBy: " ")
        let languages = [arr[0], "-"]
        let jobs = [arr[1], "-"]
        let careers = [arr[2], "-"]
        let soulFoods = [arr[3], "-"]
        let score = Int(arr[4])!

        for language in languages{
            for job in jobs{
                for career in careers {
                    for soulFood in soulFoods {
                        let key = "\(language)\(job)\(career)\(soulFood)"
                        if db[key] == nil {
                            db[key] = [score]
                        } else {
                            db[key]?.append(score)
                        }
                    }
                }
            }
        }
    }

    // 이진탐색을 위해 오름차순 정렬
    let dbCnt = db.count
    for i in db{
        let sortArr = i.value.sorted()
        db[i.key] = sortArr
    }

    // 마지막 score 비교
    for i in query{
        let arr = i.components(separatedBy: " ")
        let key = "\(arr[0])\(arr[2])\(arr[4])\(arr[6])"
        let score = Int(arr[7])!

        if let scoreArr = db[key]{
            // 이진 탐색
            var low = 0
            var high = scoreArr.count - 1
            var mid = 0

            while low <= high {
                mid = (low + high) / 2
                if scoreArr[mid] < score {
                    low = mid + 1
                } else {
                    high = mid - 1
                }
            }
            result.append(scoreArr.count - low)
        } else{
            result.append(0)
        }
    }
    
    return result
}