프로그래머스 - 순위검색

programmers.co.kr/learn/courses/30/lessons/72412

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

---

 

해당 문제는 탐색을 얼마나 효율적으로 하느냐가 중요했던 문제인 것 같다.

 

먼저 info와 query로 받은 값을 공백과 and문자를 제거해준다음 그 문자열을 key로 이용해서

해당 키에 어떤 점수의 지원자들이 있는지 파악하고 그 지원자들의 점수 중 얼마나 효율적으로 몇점 이상 지원자들을 뽑아내는지가 중요했다.

 

만약 이런 두 지원자가 존재한다면 -> "java backend junior pizza 300", "cpp frontend junior chicken 150"

dfs함수에 [java, -], [backend, -], [junior, -], [pizza, -] 두번째 지원자도 마찬가지로 지원항목 + '-' 경우까지 추가해서 모든 경우의 수를 만들어준다.

 

그리고 언어, 직군, 경력, 소울푸드까지 문자열 키가 만들어진다면 해당 지원자의 점수를 파악해서 해당 키값에 추가해준다.

 

위 2가지 지원자의 모든 경우의 수를 모두 계산하면

["cppfrontendjunior-": [150], "-frontend-chicken": [150], "javabackend-pizza": [300], "-frontend--": [150], "-frontendjunior-": [150], "--juniorpizza": [300], "-frontendjuniorchicken": [150], "---pizza": [300], "-backendjunior-": [300], "cpp-juniorchicken": [150], "cpp--chicken": [150], "java-junior-": [300], "cpp---": [150], "java-juniorpizza": [300], "cppfrontend-chicken": [150], "java---": [300], "javabackendjunior-": [300], "cppfrontend--": [150], "-backend-pizza": [300], "-backendjuniorpizza": [300], "java--pizza": [300], "cppfrontendjuniorchicken": [150], "--junior-": [300, 150], "---chicken": [150], "javabackend--": [300], "javabackendjuniorpizza": [300], "-backend--": [300], "----": [300, 150], "cpp-junior-": [150], "--juniorchicken": [150]]

 

이런식으로 모든 경우의 수가 만들어진다. 이 경우의 수는

[인재영업팀에서 지원한 지원자들의 항목별로 검색할 수 있는 조건: [해당조건의 지원자들의 점수]]

항목이 된다.

 

이렇게 모든 경우를 뽑아내고 query의 검색항목을 공백 and를 지워 키값으로 만든다음 result에서 해당 키 점수들을 찾아 조건에 맞는 점수가 몇개인지 뽑아내면 되는 문제

 

처음에는 filter함수를 이용해서 점수를 걸러내려고 했지만 시간효율 실패

두번째는 점수를 정렬한 다음 반복문을 하나만들어서 해당 점수보다 작아지면 break를 걸어 높은 점수가 몇개인지 계산했지만 시간효율에서 실패

아래는 두가지 실패 버전..

 

//반복문을 이용해 검색
var count = 0
for r in result[key]! {
  if r >= Int(point)! {
    count += 1
  } else {
    break
  }
}
answer.append(count)
             
//필터로 검색
let filter = result[key]?.filter({ $0 >= Int(point)! }).count
answer.append(filter ?? 0)

....

 

결국 도움을 받아보니 이진탐색을 이용해야 한다고...

알고리즘 문제를 풀다보면 항상 기본을 잘 알고 있어야 한다고 느낀다

 

func solution(_ info:[String], _ query:[String]) -> [Int] {
    /**
     info 와 query값의 비교를 위해 서로 공백과 and를 없애서 일치여부를 바로 확인할 수 있도록 수정해주는 함수
     */
    let info_item = info.map { $0.split(separator: " ") }
    let query_item = query.map { $0.components(separatedBy: " ").filter { $0 != "and" } }
    
    //특정 언어 직군 경력 소울푸드의 키값에 어떤 점수의 지원자가 있는지 담기 위한 변수, [특정 필터의 지원자: [지원자들의 점수들]]
    var result = [String: [Int]]()
    
    //반복문을 돌려서 모든 경우의 수를 만들어준다, 지원자 필터중 '-'는 해당 조건을 고려하지 않겠다는 뜻이므로 모든지원자들의 각 항목의 지원 분야 + '-' 두가지 항목으로 모든 경우의 수를 만들어줌
    for i in 0 ... info.count - 1 {
        dfs(depth: 0, info: [[String(info_item[i][0]), "-"], [String(info_item[i][1]), "-"], [String(info_item[i][2]), "-"], [String(info_item[i][3]), "-"], [String(info_item[i][4])]], item: [], result: &result)
    }
    
    var answer = [Int]()
    
    //이진탐색을 위해 점수 순으로 정렬을 한번 해줌
    result.forEach {
        let sortedValue = $0.value.sorted(by: <)
        result[$0.key] = sortedValue
    }
    
    query_item.forEach {
        var temp_query = $0
        let point = temp_query.removeLast()
        let key = temp_query.reduce("", +)
        if let match = result[key] {          
            var start = 0
            var end = match.count
            while start < end {
                let mid = (start + end) / 2
                if match[mid] >= Int(point)! {
                    end = mid
                } else {
                    start = mid + 1
                }
            }
            answer.append(match.count - start)
        } else {
            answer.append(0)
        }
    }
    
    return answer
}

//모든 경우의수를 만드는 함수
func dfs(depth: Int, info: [[String]], item: [String], result: inout [String: [Int]]) {
    //depth = 언어, 직군, 경력, 소울푸드 4개만 경우의수를 만들기 위한 변수
    guard depth < 4 else {
        //depth가 4보다 커지면 지금까지 만든 키값을 바탕으로 존재한다면 해당 키값의 점수값에 하나를 추가, 존재하지 않으면 해당 점수값으로 초기화
        let key = item.reduce("", +)
        if result.keys.contains(key) {
            result[key]?.append(Int(info[0][0])!)
        } else {
            result[key] = [Int(info[0][0])!]
        }
        return
    }
    
    //for문을 2번 돌려서 지원자들의 지원값, '-' 두가지로 모든 경우를 만들어냄
    for i in 0 ... 1 {
        var newItem = item
        newItem.append(info[0][i])
        var newInfo = info
        newInfo.removeFirst()
        dfs(depth: depth + 1, info: newInfo, item: newItem, result: &result)
    }
}