[Algorithm] 순위 검색

[hwangJi-dev]

💬 문제

[문제]

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

💬 Idea

• 처음에 푼 풀이 방식으로는 ‘효율성’ 테스트 케이스를 통과하지 못했다. 따라서 효율적으로 코드를 수행할 수 있는 방안을 찾아야 했다.

✅ 효율성 KeyPoint

문제 해결을 위해서, 지원자들을 그룹별로 적절하게 미리 분류해두면 매 문의 조건마다 지원자들을 INFO 배열에서 찾지 않아도 된다.

➡️ 딕셔너리를 이용하여 지원자 한명한명에게서 나올 수 있는 경우를 조합하여 만든다. [info, ‘-’]

• 이렇게 만드는 이유는 쿼리에 ‘-’ 문자가 포함되어 있을 경우가 있기 때문에 이를 고려하기 위함이다.
• 딕셔너리를 이용하면 탐색을 사용하여 값을 찾지 않고 Key값으로 접근을 할 수 있기 때문에 효율적이다.

💡 이후 이진탐색을 사용하여 딕셔너리의 쿼리 key와 일치하는 점수 value 배열을 돌며 쿼리 score보다 같거나 큰 지원자들을 색출한다.

💬 풀이

1️⃣ [1차 풀이]

var applierArray: [[String]] = []
var result: [Int] = []

func solution(_ info:[String], _ query:[String]) -> [Int] {
    for i in info {
        let arr = i.components(separatedBy: " ")
        applierArray.append(arr)
    }
    
    separateAndExecuteQuery(query)
    
    return result
}

func separateAndExecuteQuery(_ query: [String]) {
    for query in query {
        let arr = query.components(separatedBy: " ").filter{ $0 != "and" }
        executeQuery(arr)
    }
}

func executeQuery(_ query: [String]) {
    var sum = 0
    for i in applierArray {
        var isQueryRight: Bool = false
        for (index, j) in query.enumerated() {
            if index == 4 {
                if Int(i[index])! >= Int(j)! {
                    isQueryRight = true
                } else {
                    isQueryRight = false
                }
            } else {
                if j != "-" {
                    if i[index] == j {
                        isQueryRight = true
                    } else {
                        isQueryRight = false
                        break
                    }
                } 
            }
        }
        
        if isQueryRight {
            sum += 1
        }
    }
    
    result.append(sum)
}

정확도 100 / 효율성 0

소요시간 : 1시간 30분

2️⃣ [2차 풀이]

import Foundation

var applierDict: [String: [Int]] = [:]
var result: [Int] = []

func solution(_ info:[String], _ query:[String]) -> [Int] {
    for i in info {
        let arr = i.components(separatedBy: .whitespaces)
        
        // 지원자 info를 기반으로 나올 수 있는 조합
        let language = [arr[0], "-"]
        let job = [arr[1], "-"]
        let career = [arr[2], "-"]
        let food = [arr[3], "-"]
        
        for language in language {
            for job in job {
                for career in career {
                    for food in food {
                        let query = "\(language) \(job) \(career) \(food)"
                        
                        // 이미 해당 쿼리가 있다면
                        if applierDict[query] != nil {
                            // value에 점수를 append
                            applierDict[query]?.append(Int(arr[4])!)
                        } else {
                            // value에 점수를 할당
                            applierDict[query] = [Int(arr[4])!]
                        }
                    }
                }
            }
        }
    }
    
    // 점수 순으로 정렬
    for applier in applierDict {
        applierDict[applier.key] = applier.value.sorted()
    }
    
    for query in query {
        let query = query.components(separatedBy: .whitespaces)
		    let language = query[0]
		    let job = query[2]
		    let career = query[4]
		    let food = query[6]
		    let score = Int(query[7])!
		    let queryKey = "\(language) \(job) \(career) \(food)"
		    
		    // 일치하는 지원자 존재
		    if let possibilityScore = applierDict[queryKey] {
		        // 이진 탐색으로 score와 possibilityScore 비교
		        var start = 0
		        var end = possibilityScore.count
		        
						while start < end {
		            let mid = (start + end) / 2
		            if possibilityScore[mid] >= score {
		                end = mid
		            } else {
		                start = mid + 1
		            }
		        }
		        result.append(possibilityScore.count - start)
		    } else {
		        result.append(0)
		    }
    }
    
    return result
}

정확도 100 / 효율성 100