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

https://school.programmers.co.kr/learn/courses/30/lessons/72412

✍️ 첫번째 접근

query에 있는 각 원소에 점수를 가지고 info에 있는 각 원소와 비교를 하는데, 점수부터 판단하여 X점 이상 점수를 받지 못했다면 info에 있는 그 다음 원소와 비교를 한다.
정확성 테스트는 통과하였지만 효율성에서 시간 초과가 발생했다. info 배열의 크기는 1 이상 50,000 이하이고 query 배열의 크기는 1 이상 100,000 이하이므로 이를 가지고 3중 for문을 돌렸으니 당연할 결과였다.

import Foundation

func solution(_ info:[String], _ query:[String]) -> [Int] {
    
    var answer: [Int] = []
    for q in query {
        var separatedQuery = q.components(separatedBy: " ")
        separatedQuery = separatedQuery.filter { $0 != "and" }
        var cnt: Int = 0
        for i in info {
            var flag: Bool = true
            var separatedInfo = i.components(separatedBy: " ")
            if Int(separatedQuery.last!)! > Int(separatedInfo.last!)! { // 점수부터 판단
                flag = false
                continue
            }
            for s in 0..<separatedQuery.count-1 {
                if separatedQuery[s] == "-" {
                    continue
                }
                if !i.contains(separatedQuery[s]) {
                    flag = false
                    break
                }
            }
            if flag {
                cnt += 1
            }
        }
        answer.append(cnt)
    }
    return answer
}

✍️ 두번째 접근

약간의 힌트를 받아, 다시 문제를 접근하였다.
매번 query에서 설명하는 각 조건을 만족하는 지원자들을 찾는다면 통과할 수 없으므로 미리 dictionary을 사용해 지원자들을 그룹별로 분류해둔다.
key는 언어,직군, 경력, 소울 푸드로 하고 value는 key에 해당하는 값들을 저장하는 배열로 한다.
이제 X점 이상 점수를 받은 지원자를 탐색하면 되는데 효율적인 탐색을 위해 for문으로 무작정 찾는 것이 아니라 이진 탐색을 하여 해결하였다.
이번 문제에서 느낀 점은 저번과 같이 곧이곧대로 문제를 보지 말고 다른 관점에서 바라볼 수 있어야한다는 것이고, 탐색할 경우 효율성을 위해 이진 탐색을 적극 활용해야겠다는 것을 느꼈다.

import Foundation

func solution(_ info:[String], _ query:[String]) -> [Int] {
    var answer: [Int] = []
    var db: [String:[Int]] = [:]
    // 각각의 지원자 정보에 대한 경우의 수를 다 구한다.
    for i in info {
        let separatedInfo = i.components(separatedBy: " ")
        let languages = [separatedInfo[0],"-"]
        let jobs = [separatedInfo[1],"-"]
        let careers = [separatedInfo[2],"-"]
        let foods = [separatedInfo[3],"-"]
        let score = Int(separatedInfo[4])!
        for language in languages {
            for job in jobs {
                for career in careers {
                    for food in foods {
                        let key = "\(language)\(job)\(career)\(food)"
                        if db[key] == nil {
                            db[key] = [score]
                        }
                        else {
                            db[key]!.append(score)
                        }
                    }
                }
            }
        }
    }
    
    // 각 query의 점수를 가지고 이진탐색 돌린다.
    // 이진탐색을 위해 오름차순으로 정렬
    for i in db {
        let sortedValue = i.value.sorted()
        db[i.key] = sortedValue
    }
    for q in query {
        let separatedQuery = q.components(separatedBy: " ")
        let key = "\(separatedQuery[0])\(separatedQuery[2])\(separatedQuery[4])\(separatedQuery[6])"
        let score = Int(separatedQuery[7])!
        // 이진탐색 시작
        if let arr = db[key] {
            var low = 0
            var high = arr.count - 1
            var mid = 0
            while(low <= high) {
                mid = (low+high) / 2
                if arr[mid] < score {
                    low = mid + 1
                }
                else {
                    high = mid - 1
                }
            }
            answer.append(arr.count - low)
        }
        else {
            answer.append(0)
        }
    }

    return answer
}