[Swift Algorithm] 72412 순위 검색 (2021 카카오 블라인드 공채)

 

programmers.co.kr/learn/courses/30/lessons/72412

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

풀이방법

처음보고 든생각은

정보를 타입으로 분류하고

쿼리에 맞게 타입을 찾아서 반환하는 거엿죠

이정도면 레벨2에 해당하는 정도의 난이도겟거니 했지만...

 

아래는 실패한 코드구요

private func 실패solutionP72412(_ info:[String], _ query:[String]) -> [Int] {
    var result: [Int] = []
    
    struct Info {
        enum DevLanguage: String {
            case java, cpp, python
        }
        enum Job: String {
            case backend, frontend
        }
        enum Career: String {
            case junior, senior
        }
        enum Food: String {
            case chicken, pizza
        }
        
        let language: DevLanguage
        let job: Job
        let career: Career
        let soulFood: Food
        let score: Int
        
        init(_ s: String) {
            let infos = s.components(separatedBy: .whitespaces)
            self.language = DevLanguage(rawValue: infos[0])!
            self.job = Job(rawValue:  infos[1])!
            self.career = Career(rawValue: infos[2])!
            self.soulFood = Food(rawValue: infos[3])!
            self.score = Int(infos[4])!
        }
        
        func matchInfo(lang: String, job: String, career: String, food: String, score: String) -> Bool {
            var matchLang = true
            
            if lang != "-" {
                matchLang = matchLang && DevLanguage(rawValue: lang) == self.language
                if !matchLang {
                    return false
                }
            }
            if job != "-" {
                matchLang = matchLang && Job(rawValue: job) == self.job
                if !matchLang {
                    return false
                }
            }
            if career != "-" {
                matchLang = matchLang && Career(rawValue: career) == self.career
                if !matchLang {
                    return false
                }
            }
            if food != "-" {
                matchLang = matchLang && Food(rawValue: food) == self.soulFood
                if !matchLang {
                    return false
                }
            }
            matchLang = matchLang && Int(score)! <= self.score
            
            return matchLang
        }
    }
    var db: [Info] = []
    info.forEach { db.append(Info($0)) }
    
    query.forEach {
        let excuteQuery = $0.components(separatedBy: .whitespaces)
        
        let lang = excuteQuery[0]
        let job = excuteQuery[2]
        let career = excuteQuery[4]
        let soulFood = excuteQuery[6]
        let score = excuteQuery[7]
        
        var matchCount = 0
        db.forEach {
            if $0.matchInfo(lang: lang, job: job, career: career, food: soulFood, score: score) {
                matchCount += 1
            }
        }
        result.append(matchCount)
    }
    return result
}

정확성은 다맞지만 효율성에서 모두 시간초과가 나와버리더라구요..

생각해보니

info가 5만개

query가 10만개니까

for문 중첩이 잇으면 우선 절대안되겠죠 ㅎㅎ

 

다시 새로운 방법을 생각하려하는데

생각이 안나요...

 

어떻게해야 시간을 줄일까 

뭔가 logN을 사용하던가 포문 한번만 돌아야할 것같은 느낌인데

 

레벨2가 아닌 레벨2문제였구요!..

어려워서 참고좀했습니다 ㅎ...

 

 

주어진 정보에 대한 모든 조합을 미리 딕셔너리에 넣어두고 1:1 매칭이 되게하는 방법이더라구요

무슨말이냐면

"java backend junior pizza 150" 이라는 info를 받고

몇개의 조합만 해보자면 아래와 같아요

java	backend	junior	pizza
-	backend	junior	pizza
java	-	junior	pizza
java	backend	-	pizza
java	backend	junior	-
-	-	junior	pizza
-	backend	-	pizza
-	backend	junior	-
-	-	-	-

조합이 더 많겠죠?

할 수 있는 조합의 수는 16가지겠네요 2*2*2*2 가지가 있을거에요

위의 조합은 모두 같은 사람을 가르켜요

위의 쿼리를 날리면 점수 150을 받은 사람이 있다는걸 알 수 있어요

 

또 다른 정보를 작성하게 된다면 위처럼 -조합을 통해 "- - - -"는 무조건 추가될 키값이에요

"- - - -" 쿼리시 

이미 앞에서 키값으로 사용한 쿼리죠? 150점 맞은 사람을 가르키고있어요

이렇게 같은 키를 가진 사람이 또 들어올 수 있으니 배열로 저장되어야하겠네요

a점을 맞앗다고 하면

"- - - -" 쿼리시 이제 [150, a] 이렇게 나오도록 하구요

 

키값으로 쿼리문

값으로 점수배열을 가지고 있으면 돼요

 

쿼리와 1:1 매칭이기때문에 점수배열만 가지고 비교할건데

"- - - -" 와 같이 모든 점수를 저장해 놓을 수 있는 케이스가 존재 할 수도 있어요

이 때는 처음에 고려한 것 같이

5만 x 10만 케이스의 시간복잡도가 다시 성립되요

dic["- - - -"] -> [10, 20, 30, 40, 50, 60, ... n] 엄청많죠..

 

효율적으로 탐색을 하자..!

이정도는 생각나는게 이진탐색이네요

 

이진탐색을 위해서 

정보에 모든 조합을 넣엇다면 먼저 정렬을 한번해주고

비교를 하면 성공이 뜨네요!

(전체비교시 시간초과가 나요)

 

아래는 성공한 코드입니다

private func solutionP72412(_ info:[String], _ query:[String]) -> [Int] {
    var result: [Int] = []
    var db: [String: [Int]] = [:]
    
    // 정보에대한 모든 경우의 수 입력해놓기
    for s in info {
        let infos = s.components(separatedBy: .whitespaces)
        let languages = [infos[0], "-"]
        let jobs = [infos[1], "-"]
        let careers = [infos[2], "-"]
        let soulFoods = [infos[3], "-"]
        let score = Int(infos[4])!
        
        // 조합
        for lang in languages {
            for job in jobs {
                for career in careers {
                    for food in soulFoods {
                        let key = "\(lang) \(job) \(career) \(food)"
                        if db.keys.contains(key) {
                            db[key]?.append(score)
                        } else {
                            db[key] = [score]
                        }
                    }
                }
            }
        }
    }
    
    // 딕셔너리 점수순 재정렬
    for origin in db {
        let sortValue = origin.value.sorted()
        db[origin.key] = sortValue
    }
    
    // 쿼리를 키로 점수배열을 가져오고 점수배열을 이진탐색으로 효율적탐색 시도
    query.forEach {
        let excuteQuery = $0.components(separatedBy: .whitespaces)
        
        let lang = excuteQuery[0]
        let job = excuteQuery[2]
        let career = excuteQuery[4]
        let food = excuteQuery[6]
        let score = Int(excuteQuery[7])!
        
        let key = "\(lang) \(job) \(career) \(food)"
        if let matchScores = db[key] {
            // 이진 탐색
            var start = 0
            var end = matchScores.count
            while start < end {
                let mid = (start + end) / 2
                
                if matchScores[mid] >= score {
                    end = mid
                } else {
                    start = mid + 1
                }
            }
            result.append(matchScores.count - start)
            
        } else {
            result.append(0)
        }
        
    }
    return result
}