[Programmers] 순위검색

오늘은 어제 가볍게 풀려보려다가 생각치도 못한 곳에서 막힌 문제..를 풀어보았습니다. 근데 정말 알고보면 별 것도 아닌 문제였는데 ㅜ

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/72412ㅇ

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

문제 요약 

문제를 간단히 요약하면 "지원자 정보가 주어지고 이 정보들을 가지고 query문을 날려 원하는 조건의 지원자는 총 몇 명인가?"를 구하여라입니다. 문제 이해는 쉬웠어요. 

첫 풀이

import Foundation

struct Person {
    let language: String
    let job: String
    let career: String
    let soulFood: String
    let score: Int
}
func solution(_ info:[String], _ query:[String]) -> [Int] {
    var result: [Int] = []


    var people: [Person] = []


    info.enumerated().forEach {
        let seperated: [String] = $1.components(separatedBy: " ")
        let lan = seperated[0]
        let po = seperated[1]
        let ne = seperated[2]
        let so = seperated[3]
        let sc = Int(seperated[4])!

        people.append(Person(language: lan, job: po, career: ne, soulFood: so, score: sc))
    }

    query.forEach {
        var count: Int = 0
        let seperated: [String] = $0.components(separatedBy: " ")
        let lan = seperated[0]
        let po = seperated[2]
        let ne = seperated[4]
        let so = seperated[6]
        let sc = Int(seperated[7])!

        people.forEach {
            if ($0.language == lan || lan == "-") &&
                ($0.job == po || po == "-") &&
                ($0.career == ne || ne == "-")  &&
                ($0.soulFood == so || so == "-") &&
                $0.score >= sc {
                count += 1
            }
        }
        result.append(count)
    }

    return result
}

처음엔 Level 2 문제다 보니 그냥 지원자 정보에 대한 배열 만들어서 거기서 단순히 선형탐색하면 되는 문제인 줄 알았어요.

하지만 정확성과 효율성 문제를 간과 했었죠.

정확성은 다 맞긴 했는데 효율성에서 전부 시간초과가 났습니다.

다음 풀이 

info 배열은 최대 5만이고

query는 최대 10만이니 중첩 for문이 있으면 50만..

이건 피해야 했어요. 

 

그래서 아, 그럼 배열이 아니라 key로 접근해야하구나라고 생각하고

dictionary형태로 바꾸었습니다. 

key값은 Applicant 객체로 하였고 value는 지원자 점수가 담긴 배열로 했어요.

[Applicant : [Int]]

 

그런데도 '-'는 전체의 경우를 다 생각을 해야 하니 ... 더 고민이 드는 거있죠.. 

그래서 설마 '-'인 경우도 전부 dictionary에 넣어서 저장해줘야하나 생각만 했고 계속 머리 싸매다가 결국 다른 글을 참고 했네요 하하 

 

네. '-'경우도 전부 고려해서 info 하나의 문자열에 2*2*2*2 총 16개의 key값이 나와요. 

그렇게 되면 Applicant('-', '-', '-', '-') 이런 케이스도 나오겠죠..?

그리고 이건 최대 5만명이 있을 테구요. 이렇게 되면 query문 하나를 바로 접근해서 찾는다고 해도 5만개의 지원자 점수를 고려해야 하니...

중첩 for문 문제가 다시 발생해요. 

여기서는 binary search로 해결해야 하더라구요. 

 

이게 Level 2...???

쉬운 개념이긴 하지만.. 좀 더 익숙해져야겠네요.

 

import Foundation

struct Applicant: Hashable {
    let language: String
    let job: String
    let career: String
    let soulFood: String
}

func solution(_ info:[String], _ query:[String]) -> [Int] {
    var result: [Int] = []
    
    var dict: [Applicant: [Int]] = [:]
    for s in info {
        let infos = s.components(separatedBy: .whitespaces)
        let languages = [infos[0], "-"]
        let jobs = [infos[1], "-"]
        let careers = [infos[2], "-"]
        let soulFoods = [infos[3], "-"]
        let score = Int(infos[4])!
        
        for language in languages {
            for job in jobs {
                for career in careers {
                    for soulFood in soulFoods {
                        let key = Applicant(language: language, job: job, career: career, soulFood: soulFood)
                        if dict.keys.contains(key) {
                            dict[key]?.append(score)
                        } else {
                            dict[key] = [score]
                        }
                    }
                }
            }
        }
    }
    
    for applicant in dict {
        let sorted = applicant.value.sorted()
        dict[applicant.key] = sorted
    }
    
    query.forEach {
        let seperated: [String] = $0.components(separatedBy: " ")
        let language = seperated[0]
        let job = seperated[2]
        let career = seperated[4]
        let soulFood = seperated[6]
        let score = Int(seperated[7])!
        let key = Applicant(language: language, job: job, career: career, soulFood: soulFood)
        if dict.keys.contains(key) {
            // 이진 탐색
            let scores = dict[key]!
            var low = 0
            var high = scores.count
            
            while low < high {
                let mid = (low + high) / 2
                let guess = scores[mid]
                if guess >= score {
                    high = mid
                } else {
                    low = mid + 1
                }
            }
            result.append(scores.count - low)
        } else {
            result.append(0)
        }
    }
    return result
}

참고자료 

- https://velog.io/@sainkr/프로그래머스-순위-검색-Swift