[프로그래머스] 순위 검색 (C++, Swift)

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

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

카카오 2021

 

접근방법

쿼리당 맞는 참가자를 일일이 검사하는 방법도 있지만 그런식으로는 효율성 테스트를 통과하지 못한다.

 

지원자의 정보를 담은 문자열을 가공해서 해당 지원자가 들어맞을 수 있는 모든 쿼리 경우를 만들어서 딕셔너리에 지원자의 점수와 함께 저장한다.

딕셔너리는 [지원자가 해당될 수 있는 쿼리의 문자열 : [이 쿼리에 해당하는 지원자의 점수를 담은 배열] ]이다.

 

예를들어 java backend junior pizza 150인 지원자가 있다면

javabackendjuniorpizza 

-backenjuniorpizza

java-juniorpizza

javabackendjunior-

--juniorpizza

java--pizza

javabackend--

-backend-pizza

... 등 내가 해당될 수 있는 모든 쿼리를 만들어야 한다.

 

딕셔너리가 완성되면 딕셔너리의 요소(key, value)마다 value(배열)를 정렬해야한다. 즉, 점수 배열을 오름차순으로 정렬해야한다.

 

그 다음 쿼리마다 해당 쿼리에 맞는 딕셔너리 원소를 보고, value(즉, 해당 쿼리에 맞는 지원자의 점수 배열)에서 쿼리가 원하는 점수 이상인 지원자의 수를 구해야한다. 단, 이는 이분탐색으로 구해야한다. (점수 배열을 정렬한 이유이다)

 

끝

 

오답노트

C++로 풀었을때와 같은 실수를 했는데, 딕셔너리의 점수배열을 쿼리 마다 정렬했다는 점이었다.

딕셔너리의 크기보다 쿼리의 크기가 더 클 수 있기 때문에 (쿼리가 10만까지 있을 수 있다) 쿼리에 의해 불릴지 모르는 딕셔너리 요소도 정렬해두는게 더 효율적이다.

 

소스코드

Swift

import Foundation

var infoDic:[String:[Int]] = [String:[Int]]()

func solution(_ info:[String], _ query:[String]) -> [Int] {
    makeInfoDic(info)
    sortInfoDicValues()
    let result:[Int] = makeResult(query)
    return result
}

func makeInfoDic(_ infos:[String]) {
    for info in infos {
        var infoToArray:[String] = info.components(separatedBy:" ")
        let applicantScore:Int = Int(infoToArray.last ?? "0") ?? 0
        infoToArray.removeLast()
        addApplicantInfoToInfoDic(0, "", infoToArray, applicantScore)
    }
}

func addApplicantInfoToInfoDic(_ index:Int, _ infoStr:String, _ info:[String], _ applicantScore:Int){
    if index == info.count {
        if infoDic[infoStr] == nil {
            infoDic[infoStr] = [applicantScore]
        } else {
            infoDic[infoStr]?.append(applicantScore)
        }
        return
    }
    
    addApplicantInfoToInfoDic(index+1, infoStr+info[index], info, applicantScore)
    addApplicantInfoToInfoDic(index+1, infoStr+"-", info, applicantScore)
}


func sortInfoDicValues() {
    for (info, scores) in infoDic {
        infoDic[info] = scores.sorted()
    }
}

func makeResult(_ query:[String]) -> [Int] {
    var result:[Int] = [Int]()

    for q in query {
        let componentsOfQuery:[String] = q.components(separatedBy:" ").filter{$0 != "and"}
        let queryScore:Int = Int(componentsOfQuery.last ?? "0") ?? 0
        let queryString:String = componentsOfQuery[..<(componentsOfQuery.count-1)].joined()
        result.append(getNumOfApplicantMatchedToQuery(queryString, queryScore))
    }
    
    return result
}


func getNumOfApplicantMatchedToQuery(_ query:String, _ queryScore:Int) -> Int {
    if infoDic[query] != nil {
        return infoDic[query]!.count - getLowerBound(infoDic[query]!, queryScore)
    } else {
        return 0
    }
}

func getLowerBound(_ array:[Int], _ target:Int) -> Int {
    var start = 0
    var end = array.count
    
    while start < end {
        let mid: Int = (start + end) / 2
        if target <= array[mid] {
            end = mid
        } else {
            start = mid + 1
        }
    }

    return start
}

C++

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;
unordered_map<string, vector<int>> infoMap;
string token;

void getInfoMap(vector<vector<string>> infoTokens){
    for(vector<string> aInfo : infoTokens){
        // 한 사람에 대한 정보
        int score = stoi(aInfo[4]);
        infoMap["----"].push_back(score);
        infoMap[aInfo[0] + aInfo[1] + aInfo[2] + aInfo[3]].push_back(score);
        
        // - 개수별 문자열 순열 구하기
        for(int k = 1 ; k <= 3 ; k++){
            vector<int> permu(4-k, 0);
            for(int i = 0 ; i < k ; i++){
                permu.push_back(1);
            }
            
            do {
                // 하나의 문자열 완성
                string infoCase = "";
                for(int i = 0 ; i < 4 ; i++){
                    if(permu[i] == 1){
                        infoCase += aInfo[i];
                    }else{
                        infoCase += '-';
                    }
                }
                infoMap[infoCase].push_back(score);
            } while(next_permutation(permu.begin(), permu.end()));
        }
    }
}

vector<vector<string>> getInfoVector(vector<string> info){
    vector<vector<string>> result(info.size());
    for(int i = 0 ; i < info.size() ; i++){
        //한명 정보 정리
        istringstream iss(info.at(i));
        while(getline(iss, token, ' ')){
            result[i].push_back(token);
        }
    }
    return result;
}

vector<vector<string>> getQueryVector(vector<string> query){
    vector<vector<string>> result(query.size());
    for(int i = 0 ; i < query.size() ; i++){
        //쿼리 하나 정보 정리
        istringstream iss(query.at(i));
        while(getline(iss, token, ' '))
            result[i].push_back(token);
    }
    return result;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    vector<vector<string>> realInfo = getInfoVector(info);
    vector<vector<string>> realQuery = getQueryVector(query);   
    getInfoMap(realInfo);
    
    for(auto &im : infoMap){
        sort(im.second.begin(), im.second.end());
    }
        
    for(vector<string> q : realQuery){
        int minScore = stoi(q[7]);
        vector<int> candi = infoMap[q[0]+q[2]+q[4]+q[6]];
        int startIdx = lower_bound(candi.begin(), candi.end(), minScore) - candi.begin();
        answer.push_back(candi.size() - startIdx);
    }
    
    
    return answer;
}