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

🕵🏻  문제 해석

---

카카오의 하반기 경력 개발자 공개채용에서 지원자들의 지원서와 코딩테스트 점수를 이용하여 채용에 참여한 개발팀들의 문의 사항에 맞는 지원자들의 수를 제공하려고 합니다. 지원서 항목은 총 4가지, 개발언어, 지원 직군, 지원 경력, 선호하는 소울푸드로 구성되어있습니다. 

따라서 지원서의 4가지 항목, 코딩테스트 점수 1가지, 총 5가지의 항목을 자료구조에 저장하고 문의 사항들을 탐색하며 각각 기준을 충족하는 지원자들의 수를 구하면 될 것 같습니다. 

그렇게 하기위해 Key는 지원자가 충족하는 조건을 의미하는 String, Value는 해당 조건을 만족하는 지원자들의 점수 배열 [Int] 형태의 딕셔너리에 지원자들의 정보를 저장해보겠습니다.

 var dic: [String : [Int]] = [:]

• info : "java backend junior pizza 150"
• query : "java and backend and junior and pizza 150"

딕셔너리에 저장하기 전에, 먼저 입력을 살펴보면 주어지는 지원자들의 정보는 공백 (" ")으로 구분되어있고 반면에 개발팀들의 문의사항은 공백과 (" "), ("and")로 구분되어있습니다. 먼저 이를 동일한 형태로 만들어 주어야 비교를 할 수 있게 되겠죠?

for applicant in info {
	// applicant -> "java backend junior pizza 150"
       
        var components = applicant.components(separatedBy: " ")
        
        // components -> ["java", "backend", "junior", "pizza", "150"]
        let score = Int(components[4])!
}

for q in query {
    	// q -> "java and backend and junior and pizza and 150"
    
        var components = q.components(separatedBy: " ").filter{$0 != "and"}
        
        // components -> ["java", "backend", "junior", "pizza", "150"]
        let score = Int(components[4])!
 }

자주 사용하는 components 메서드를 이용하여 공백을 기준으로 나눈 [String] 배열로 지원자의 정보를 나눌 수 있습니다. 그 후 코딩테스트의 점수는 Int 생성자를 이용하여 따로 처리합니다.  마찬가지로 query도 처리해준 후, filter를 이용하여 "and"를 걸러냅니다.

여기서 문의사항 안의 "-" 항목 때문에 골치가 아파집니다. 

만약 지원자의 정보가 "java backend junior pizza 150" 로 주어지면 점수를 제외하고 지원자가 충족하는 조건이 총 16가지가 됩니다. 

["java", "backend", "junior", "pizza"]
["java", "backend", "junior", "-"]
["java", "backend", "-", "pizza"]
["java", "backend", "-", "-"]
["java", "-", "junior", "pizza"]
["java", "-", "junior", "-"]
["java", "-", "-", "pizza"]
["java", "-", "-", "-"]
["-", "backend", "junior", "pizza"]
["-", "backend", "junior", "-"]
["-", "backend", "-", "pizza"]
["-", "backend", "-", "-"]
["-", "-", "junior", "pizza"]
["-", "-", "junior", "-"]
["-", "-", "-", "pizza"]
["-", "-", "-", "-"]

따라서 재귀함수를 이용하여 지원자가 충족하는 조건들의 모든 케이스들을 구해주어 딕셔너리에 점수를 저장해 주겠습니다. 

 // arr: 지원자들의 정보를 담은 배열
 // curIdx: "-"로 바꿔 저장할 항목의 인덱스
 // score: 지원자의 점수
 
 func combination(_ arr: [String], _ curIdx: Int, _ score: Int) {
        if curIdx == arr.count {
            let result = arr.joined()
            
            // 항목들을 하나의 문자열로 합쳐서 딕셔너리에 점수를 저장
            if dic[result] != nil {
                dic[result]!.append(score)
            } else {
                dic[result] = [score]
            }
        } else {
            var temp = arr
            
            combination(temp, curIdx + 1, score)
            temp[curIdx] = "-"
            combination(temp, curIdx + 1, score)
        }
        return
   }

저장이 끝나면 이 후 이분 탐색을 위해 딕셔너리의 [Int] 배열을 오름차순으로 정렬해줍니다. 이제 쿼리들을 탐색하며 딕셔너리에 점수 배열이 존재하면 쿼리의 점수와 비교하여 그 개수를 answer배열에 추가하고 존재하지 않으면 해당 조건을 만족하는 지원자가 없으므로 0을 추가합니다. 

이때 문제에서는 지원자가 최대 5만 명이고 점수의 최댓값은 10만 점, 쿼리 배열의 최대 크기가 10만이라고 합니다. 지원자들의 점수가 모두 다르다고 가정할 수 있으므로 선형 탐색으로는 시간 초과가 날 수 있습니다. 이분 탐색을 이용하여, LowerBound를 구해 요구 점수 이상의 점수들을 카운트해줍니다.

📦  문제 풀이 & 코드

---

import Foundation

func solution(_ info:[String], _ query:[String]) -> [Int] {
    var dic: [String : [Int]] = [:]
    var answer = [Int]()
    
    func combination(_ arr: [String], _ curIdx: Int, _ score: Int) {
        if curIdx == arr.count {
            let result = arr.joined()
            
            if dic[result] != nil {
                dic[result]!.append(score)
            } else {
                dic[result] = [score]
            }
        } else {
            var temp = arr
            combination(temp, curIdx + 1, score)
            temp[curIdx] = "-"
            combination(temp, curIdx + 1, score)
        }
        return
    }
    
    func lowerbound(_ arr: [Int], _ score: Int) -> Int {
        var low = 0
        var high = arr.count
        
        while low < high {
            let mid = (low + high) / 2
            if score <= arr[mid] {
                high = mid
            } else {
                low = mid + 1
            }
        }
        // low = score 이상의 점수가 처음 등장하는 인덱스
        return arr.count - low
    }
    
    for applicant in info {
        var components = applicant.components(separatedBy: " ")
        let score = Int(components[4])!
        components.removeLast()
        combination(components, 0, score)
    }
    
    // 이분탐색을 위해 미리 점수배열을 정렬
    for (query, scores) in dic {
        let sortedScores = scores.sorted(by: <)
        dic[query] = sortedScores
    }

    for q in query {
        var components = q.components(separatedBy: " ").filter{$0 != "and"}
        let score = Int(components[4])!
        components.removeLast()
        let key = components.joined()
        
        // 해당 조건을 충족하는 점수가 없다면 0
        if dic[key] == nil {
            answer.append(0)
        } else {
        // 해당 조건을 충족하는 점수 배열이 존재하면, 쿼리의 요구 점수로 이분 탐색
            answer.append(lowerbound(dic[key]!, score))
        }
    }
    return answer
}

 

🤷🏻‍♂️ 더 생각해보기

---

힘들게 통과.. 😿

처음 문제에 접근할 때는 단순히 쿼리와 지원자들의 정보를 다중 for문을 통해 비교해주었습니다. 테스트 케이스는 모두 통과했으나 효율성 테스트에서 시간 초과가 나더군요..

문제의 조건을 찾아보니 지원자들의 최대 수가 5만, 쿼리 배열의 최대 크기가 10만이니 단순 곱만 해봐도 50억이 넘어갑니다. 이번에는 혼자 해결하지 못하고 다른 분들의 풀이를 참고하여 문제를 다시 풀어보았습니다.

효율성 테스트에서도 시간이 꽤 걸리는 것으로 보아 입력으로 들어온 지원자 정보와 쿼리를 나누어 저장할 때 filter {} 대신에 and가 등장하는 인덱스는 정해져 있으므로 특정 인덱스만을 모아 "\(components [0])\(components [2])..."이런 식으로 처리하면 더 빠른 속도로 통과할 수 있을 것 같습니다.

👍🏻 참고

---

• https://nsios.tistory.com/128