프로그래머스 - 순위검색 Swift

https://programmers.co.kr/learn/courses/30/lessons/72412?language=swift 

코딩테스트 연습 - 순위 검색

 

 

정확성만을 묻는 문제였다면 1단계에 있었어도 무방했겠으나,

효율성까지 구현하려고 보니 이게 2단계에 있는 게 맞는건가? 하는 생각이 들었던 문제.

 

처음 구현을 시도했을 때에는 O(n3)이 아니라 O(n2)까지 줄여보라는 말이구나! 해서 아래와 같이 시도했다가...

틀려버렸다.

var answerArray = [Int]()
    var infoArrays = info.map({$0.components(separatedBy: " ")})
    var queryArrays = query.map({String($0.replacingOccurrences(of: "and ", with: "")).components(separatedBy: " ")})

    for (index, element) in queryArrays.enumerated() {
        var a = 0
        for (i, info) in infoArrays.enumerated() {
            if ((info[0] == element[0] || element[0] == "-") &&
               (info[1] == element[1] || element[1] == "-") &&
               (info[2] == element[2] || element[2] == "-") &&
               (info[3] == element[3] || element[3] == "-") &&
               Int(info[4])! >= Int(element[4])!) {
               a += 1 
            }
        }
        answerArray.append(a)
    }

 

그래서 다른 사람의 블로그를 찾아서 검색해본 결과,

이 문제의 핵심 로직에는 두 가지 접근법이 있었다.

 

첫째는 모든 key를 database라는 변수에 저장해놓는 것.

담을 때에는 "-" 또한 고려하여 넣어줬다.

예를 들어 language로 Java가 들어온다면 "Java", "-" 모두 고려했다는 것.

 

둘째는 이진 탐색을 이용해야 한다는 것.

사실 database에 모든 key를 저장해놓는 것은 시간 복잡도의 계수를 고려하지 않았을 때 이미 O(n)이라서 충분하다고 생각했다. 그런데 이러한 접근법으로만 풀었을 때의 결과는 fail이다.

즉, 계수까지 고려해 이진 탐색을 이용해야 한다는 것인데, 

예를 들어 어떤 database[key]의 value 배열이 문제에서 주는 최대 길이(50000)일 때 

처음부터 끝까지 다 돌면 50,000번이고 query의 최대 개수는 100,000이므로 

최악의 경우 5,000,000,000번, 즉 50억번 돌아야 하므로 시간초과가 난다.

때문에 아래 정답 코드의 맨 아래 로직처럼 이진 탐색을 적용해주어야 시간초과를 피할 수 있다.

(참고로 아래 코드도 통과는 하지만 엄청나게 오래 걸린다.)

 

import Foundation

func solution(_ info:[String], _ query:[String]) -> [Int] {
    
    var answerArray = [Int]()
    
    var database = [String: [Int]]()
    
    for (index, element) in info.enumerated() {
        var information = element.components(separatedBy: " ")
        
        var languages: [String] = [information[0], "-"]
        var backFronts: [String] = [information[1], "-"]
        var careers: [String] = [information[2], "-"]
        var soulFoods: [String] = [information[3], "-"]
        
        for language in languages {
            for backFront in backFronts {
                for career in careers {
                    for soulFood in soulFoods {
                        var key = "\(language)\(backFront)\(career)\(soulFood)"
                        if database[key] == nil {
                            database[key] = [Int(information[4])!]
                        } else { // 이미 하나 이상 있다는 소리.
                            database[key]!.append(Int(information[4])!)
                        }
                    }
                }
            }
        }        
    }
    // 이진 탐색을 위한 db value sort
    for db in database {
        database[db.key] = db.value.sorted()
    }
    
    for (i, e) in query.enumerated() {
        
        var q = e.components(separatedBy: " ")
        var lang = q[0]
        var backFront = q[2]
        var career = q[4]
        var soulFood = q[6]
        var score = Int(q[7])!
        
        if let values: [Int] = database["\(lang)\(backFront)\(career)\(soulFood)"] {
            var lowIndex = 0
            var highIndex = values.count
            
            while lowIndex < highIndex {
                let midIndex = (lowIndex + highIndex) / 2
                if (score <= values[midIndex]) {
                    highIndex = midIndex
                } else {
                    lowIndex = midIndex + 1
                }
            }
            
            answerArray.append(values.count - lowIndex)
        } else {
            answerArray.append(0)
        }
    }

    
    return answerArray
}