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

2단계 문제인데 생각보다 시간이 안나와서 결국 정확성 테스트만 맞춘 문제입니다..

 

<내가 짠 코드> 

약간 무식하게 문제 그대로 짰는데 시간이 정말 길게 나옵니다.. 그래도 배열을 다루는 여러 메서드를 알게 된 문제였습니다.

정확성 테스트 O, 효율성 테스트 X

import Foundation

func solution(_ info:[String], _ query:[String]) -> [Int] {
    
    var result: [Int] = Array(repeating: 0, count: query.count)
    var count: Int = 0
    
    for q in query {
        var checkElements: [String] =  q.components(separatedBy: " ")
        
        for i in 0..<checkElements.count {
            checkElements[i] = checkElements[i].trimmingCharacters(in: .whitespaces)
        }
        checkElements = checkElements.filter { $0 != "and" }
        let conditionScore: Int = Int(checkElements.last!)!
        checkElements.removeLast()
        
        
        for candidate in info {
            let candiScore: Int = Int(candidate.components(separatedBy: " ").last!)!
            let scoreCheck: Bool = candiScore >= conditionScore
            var temp: Bool = true
            for condition in checkElements {
                if ( condition == "-" || candidate.contains(condition) ) && scoreCheck {
                   continue
                }
                else {
                    temp = false
                    break
                }
            }
            if temp {
                result[count] += 1
            }
            
        }
        count += 1
    }
    return result
}

 

 

아래는 다른 분의 코드 -> 카카오 공식을 보면 이게 정석적 풀이인듯 합니다.

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)
                        }
                    }
                }
            }
        }
    }

    for i in db{
        let sortArr = i.value.sorted()
        db[i.key] = sortArr
    }

	// 쿼리별 세기
    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
}

print(solution(["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"],["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"]))

이걸 조금 내 스타일 대로 바꿔보고자 쿼리에서 찾는 것을 바꿔보기도 했으나 결국 효율성에서 fail이 났습니다..
진짜 정석대로 풀어야 통과인가 봅니다.

 

암튼 풀이의 간단한 설명은..

먼저 -을 포함한 모든 경우의 수를 딕셔너리로 만들고 이를 탐색하는 알고리즘입니다.

query를 찾는 것은 중간 값 부터 탐색을 하는 알고리즘을 사용해 불필요한 연산을 줄인 코드였습니다.