プログラマレベル2

こんにちは!禹元です.
プログラマーの質問に答えました.
2021 KAKAO BLIND RECRUITMENT
ランキング検索
もう4千余りの問題をやった.私ももちろん解きます.いいと思った.始まります!

問題を見ると、まずテーマは「検索」です.効率性はテスト対象にも含まれる可能性があるという意味です.指紋自体は少し長いですが、難解な問題ではありません.与えられたqueryに基づいてAND条件レコードを抽出するだけである.効率性が気になるが、最初は単純に調査を伝授しただけで、重なるためだった.

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

using namespace std;

vector<string> split(string input, char delimeter)
{
    vector<string> answer;
    stringstream ss(input);
    string temp;

    while (getline(ss,temp,delimeter))
    {
        answer.push_back(temp);
    }
    return answer;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer(query.size()); // 초기화
    vector<vector<string>> table;

    for (int i = 0; i < info.size(); i++)
    {
        vector<string> temp = split(info[i],' ');
        table.push_back(temp);
    }
    
    for (int i = 0; i < query.size(); i++)
    {
        vector<string> temp = split(query[i], ' ');
        int indicator = 0; //5가지의 조건을 충족하면 5가 된다
        for (int j = 0; j < table.size(); j++)
        {
            indicator = 0;
            //0 언어 
            //2 직군
            //4 경력
            //6 소울푸드
            //7 점수
            if (temp[0] == "-")
                indicator += 1;
            else
            {
                vector<string>::iterator i = find(table[j].begin(), table[j].end(), temp[0]);

                if (i != table[j].end())
                    indicator += 1;
            }

            if (temp[2] == "-")
                indicator += 1;
            else
            {
                vector<string>::iterator i = find(table[j].begin(), table[j].end(), temp[2]);

                if (i != table[j].end())
                    indicator += 1;
            }

            if (temp[4] == "-")
                indicator += 1;
            else
            {
                vector<string>::iterator i = find(table[j].begin(), table[j].end(), temp[4]);

                if (i != table[j].end())
                    indicator += 1;
            }

            if (temp[6] == "-")
                indicator += 1;
            else
            {
                vector<string>::iterator i = find(table[j].begin(), table[j].end(), temp[6]);

                if (i != table[j].end())
                    indicator += 1;
            }
           
            if (stoi(table[j][4]) >= stoi(temp[7]))
                indicator += 1;

            if (indicator == 5)
                answer[i] += 1;
        }
    }

    return answer;
}

違うわけじゃない...正確性はすべて通過したが、効率はまだ待っている.
効率を向上させるためには、コードを改善しなければなりません.
まず改良されたのは低減演算である.その後,不要な探索と繰返しを取り除き,コードを最大限簡潔に修正する.

코드를 입vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer(query.size()); // 초기화

    for (int i = 0; i < query.size(); i++)
    {
        vector<string> temp = split(query[i], ' ');
        for (int j = 0; j < info.size(); j++)
        {
            if (temp[0] != "-" && info[j].find(temp[0]) == string::npos)
                continue;
            if (temp[2] != "-" && info[j].find(temp[2]) == string::npos)
                continue;
            if (temp[4] != "-" && info[j].find(temp[4]) == string::npos)
                continue;
            if (temp[6] != "-" && info[j].find(temp[6]) == string::npos)
                continue;
            int score = extractor(info[j]);
            if (score < stoi(temp[7]))
                continue;
            else
                answer[i] += 1;
        }
    }

    return answer;
}력하세요

精度テストでも実行時間が短縮されましたが...しかし、結果は惨めで見るに忍びない.

それから私はずっと試していました...何度も失敗したが、仕方なくグーグルで他のコードを見るしかなかった.

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

using namespace std;

unordered_map<string, vector<int>> scores;
string s[4], num;


void getCombi(int num) {
    for (int i = 0; i < 16; i++)
    {
        string tmp = "";

        for (int j = 0; j < 4; j++)
        {
            if (i & (1 << j))tmp.push_back('-');
            else tmp += s[j];
        }
        scores[tmp].push_back(num);
    }
}

// upper_bound() -> 원하는 범위에서 입력한 인자를 초과하는 주소를 반환
// lower_bound() -> 원하는 범위에서 입력한 인자 이상인 값이 시작하는 주소를 반환

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer; // 초기화
    
    for (auto& i : info)
    {
        stringstream ss(i);
        ss >> s[0] >> s[1] >> s[2] >> s[3] >> num;
        getCombi(stoi(num)); // 4가지 조건이 있기 때문에 총 조합할 수 있는 조합의 갯수는 16가지
    }

    for (auto& s : scores)
    {
        sort(s.second.begin(), s.second.end());
    }

    for (auto& q : query)
    {
        int score;
        stringstream ss(q);
        ss >> s[0] >> num >> s[1] >> num >> s[2] >> num >> s[3] >> num;
        score = stoi(num);

        vector<int> v = scores[s[0] + s[1] + s[2] + s[3]];
        if (v.size() != 0)
        {
            auto it = lower_bound(v.begin(), v.end(), score);
            answer.push_back(v.size() - (it - v.begin()));
        }
        else {
            answer.push_back(0);
        }
    }

    return answer;
}

他のコードでは,mapと無秩序mapとしてlow bound()STL関数を用いて問題を解決することが多い.時間的複雑さをO(logn)に低減するためのバイナリ探索法は,解決効率に決定的な役割を果たした.問題を解くが、詰まる問題を見るたびに息が詰まる.私はどうしてもっと卓越した考えがないのですか...そう思います.
しかし、まだ解けています.失敗しても解き直す.
ゆりかごからコードへ
ありがとうございます.