티스토리 뷰

728x90

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

 

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

["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"] ["java and backend and junior and pizza 100","pyt

programmers.co.kr

카카오 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;
}
728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함