[Swift 알고리즘] 프로그래머스(Lv.2) - 순위 검색 / 2021 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 순위 검색" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 2렙 코스프레 문제입니다.

조합과 이분 탐색을 이용하는 문제입니다.

 

1. 각 info에 대응하는 모든 조합을 구합니다.

info와 query의 범위가 넓어 다중 반복문으로 해결할 수 없습니다.

와일드카드가 포함된 것 중 이 지원 정보가 될 수 있는 경우의 수를 모두 만드는 겁니다.

지원 정보: [코딩테스트 점수 쌍]으로 해시 테이블을 구성합니다. (value는 배열입니다.)

 

예를 들어 "java backend junior pizza 150"라면 

1. javabackendjuniorpizza : 150

2. javabackendjunior- : 150

3. javabackend-- : 150

...

 

이런 형태입니다.

 

모든 info에 대해 위 작업을 하여 해시 테이블을 구성합니다.

 

2. 이분 탐색을 이용해 코딩 테스트 점수를 넘은 사람 수를 구합니다.

각 query마다 반복문으로 코딩 테스트 점수를 체크해도 시간 초과가 발생합니다.

그래서 이분 탐색을 사용해줘야 해요. 사전에 코딩 테스트 점수를 오름차순 정렬 해야 합니다.

 

만약 query에 대한 key값이 해시테이블에 없다면 0을 result 배열에 넣습니다.

key값이 해시 테이블에 있다면 요구하는 점수가 나올 때까지 이분 탐색을 해주세요.

 

구해졌다면 그 점수 이상인 사람 수를 구해야하니 scores.count - low 를 합니다.

 

후기

2레벨인데 정말 어려웠습니다.

일단 모든 조합을 구성해서 해시테이블로 해결한다는 발상부터 막막한 거 같아요.

2021년에 무슨 일이 있었는지 모르겠습니다.

 

감사합니다!

---

전체 코드

import Foundation

func solution(_ info:[String], _ query:[String]) -> [Int] {
    var result: [Int] = []
    var cases: [String: [Int]] = [:]
    
    for info in info {
        let info = info.components(separatedBy: " ")
        let lang = [info[0], "-"]
        let job = [info[1], "-"]
        let career = [info[2], "-"]
        let food = [info[3], "-"]
        
        var scores: [Int] = []
        
        for lang in lang {
            for job in job {
                for career in career {
                    for food in food {
                        let str = lang + job + career + food
                        let score = Int(info[4])!
                        scores.append(score)
                        if let _ = cases[str] {
                            cases[str]?.append(score)
                        } else {
                            cases[str] = [score]
                        }
                    }
                }
            }
        }
    }
    
    cases.keys.forEach { cases[$0]?.sort(by: <) }
        
    for query in query {
        var query = query.components(separatedBy: " ").filter { $0 != "and" }
        let score = Int(query.popLast()!)!
        
        guard let scores = cases[query.joined()] else {
            result.append(0)
            continue
        }
        
        var low = 0
        var high = scores.count - 1
        var mid = 0
        
        while low <= high {
            mid = (low + high) / 2
            if scores[mid] < score {
                low = mid + 1
            } else {
                high = mid - 1
            }
        }
        
        result.append(scores.count - low)
    }
    
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.