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

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

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

 

지금도 물론 잘 모르지만, 더 모를 시절에 응시했던 2021 카카오 블라인드 채용 문제이다. 

그 때 봤을 때는 풀지 못했는데, 그래도 이번에는 어느정도 접근은 가능했다. 

 

이전에 답안이 나왔을 때 한 번 봐서 그런지 대략적인 풀이법은 인지하고 있었기에 그리 어렵지 않게 풀이했다. 

과정은 아래와 같다. 

 

1. info를 db화 하기 (4요소를 경우의 수를 따져 미리 저장해두기 

2. db를 val 기준으로 오름차순 정렬하기

3. query를 돌며 db의 key에 있는지 확인

      3-1. db[key]의 배열과 query의 score를 비교해야함 > 이분탐색 

      3-2. query의 score보다 높은 점수의 개수를 세서 append

4. db에 없다면 0 추가 

 

경우의 수를 따져서 key, value 쌍으로 만들어둔다는게 핵심 아이디어인 것 같다. 

사실 O(nm)의 복잡도로 풀이되는 방법만 알고있었는데, 이는 효율적이지 못하기에 위 처럼 경우의 수를 구해두고 query와 비교하는 것이 더 효율적인 것 같다. 

 

import Foundation

func solution(_ info:[String], _ query:[String]) -> [Int] {
    // 문자열 요소를 배열로!
    var info = info.map {$0.replacingOccurrences(of: " and", with: "").components(separatedBy: " ")}
    // db를 딕셔너리로
    var db = [String:[Int]]()
    // 결과
    var ans = [Int]()
    
    // db 구성
    for data in info {
        let lang = [data[0],"-"]
        let dev = [data[1],"-"]
        let lev = [data[2],"-"]
        let food = [data[3],"-"]
        let score = Int(data[4])!
        
        // 모든 케이스를 key value로 저장 
        for l in lang {
            for d in dev {
                for v in lev {
                    for f in food {
                        var datas = "\(l)\(d)\(v)\(f)"
                        if let _ = db[datas] {
                            db[datas]!.append(score)
                        } else {
                            db[datas] = [score]
                        }
                    }
                }
            }
        }
    }
    
    // value를 기준으로 오름차순 정렬 
    for d in db {
        let val = d.value.sorted {$0 < $1}
        db[d.key] = val
    }
    
    // 쿼리를 돌면서
    for q in query {
        // 우선 문자열 전처리
        var t = q.replacingOccurrences(of:" and", with:"").components(separatedBy: " ")
        // key 설정
        var k = "\(t[0])\(t[1])\(t[2])\(t[3])"
        // 점수
        var score = Int(t[4])!
        
        // 키에 대응되는 score 배열
        if let val = db[k] {
            // 이분탐색
            var left = 0 
            var right = val.count - 1 
            var mid = 0
            
            while left <= right {
                mid = (left + right) / 2
                
                if val[mid] < score {
                    left = mid + 1
                } else {
                    right = mid - 1
                }
            }
            // left 이후는 기준 score 이상의 점수들임!
            ans.append(val.count - left)
            
        } else {
            // db에 key가 없을 때 
            ans.append(0)
        }
        
    }
    
    return ans
}

문자열 + 이분탐색 그리고 db화 하는 초기 아이디어가 중요했던 문제인 것 같다!