Make Unreal REAL.
article thumbnail
Published 2023. 8. 16. 10:24
Level 2. 순위 검색 자료구조 & 알고리즘/프로그래머스
Level 2. 순위 검색

 

 

레벨 2가 맞나 싶을 정도로 파싱, 해시, 이진 탐색 그리고 효율성까지 정말 다양한 것들을 잘 알고 활용해야 하는 카카오 문제다.

  • 꽤 어려웠지만 나름 성장했다고 느낀다.

 

우선 첫 번째 시도에서 시간 초과가 발생했다.

  • 파싱은 정규 표현식을 이용해 and를 없애고 istringstream을 이용했다.
  • 이후 언어부터 점수까지 조건에 맞는 인덱스를 구하는 방식으로 해결했다.
    [0, 1, 2, 3, 4, 5, 6, 7]
    [0, 2, 3, 5, 7]
    [0, 5, 7]
    [0, 5]
    [5]

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <regex>
#include <sstream>
#include <numeric>
#include <algorithm>

using namespace std;

enum class LANG   { CPP, JAVA, PYTHON, ANY };
enum class PART   { BACKEND, FRONTEND, ANY };
enum class CAREER { JUNIOR, SENIOR, ANY };
enum class FOOD   { CHICKEN, PIZZA, ANY };

struct Info
{
    LANG lang;
    PART part;
    CAREER career;
    FOOD food;
    int score;
};

Info parse(string& query_string)
{
    Info info;
    istringstream iss(regex_replace(query_string, regex("and"), ""));

    string s;
    int score;

    iss >> s;
    info.lang = (s[0] == 'j') ? LANG::JAVA : (s[0] == 'c') ? LANG::CPP : (s[0] == 'p') ? LANG::PYTHON : LANG::ANY;
    iss >> s;
    info.part = (s[0] == 'b') ? PART::BACKEND : (s[0] == 'f') ? PART::FRONTEND : PART::ANY;
    iss >> s;
    info.career = (s[0] == 'j') ? CAREER::JUNIOR : (s[0] == 's') ? CAREER::SENIOR : CAREER::ANY;
    iss >> s;
    info.food = (s[0] == 'c') ? FOOD::CHICKEN : (s[0] == 'p') ? FOOD::PIZZA : FOOD::ANY;
    iss >> score;
    info.score = score;

    return info;
}

int filter(vector<Info>& db, Info query)
{
    vector<int> input(db.size()), result;

    iota(input.begin(), input.end(), 0);
    if (query.lang == LANG::ANY)
        result = input;
    else
        copy_if(input.begin(), input.end(), back_inserter(result), [&](int i) { return (db[i].lang == query.lang); });

    input.clear();
    if (query.part == PART::ANY)
        input = result;
    else
        copy_if(result.begin(), result.end(), back_inserter(input), [&](int i) { return (db[i].part == query.part); });

    result.clear();
    if (query.career == CAREER::ANY)
        result = input;
    else
        copy_if(input.begin(), input.end(), back_inserter(result), [&](int i) { return (db[i].career == query.career); });

    input.clear();
    if (query.food == FOOD::ANY)
        input = result;
    else
        copy_if(result.begin(), result.end(), back_inserter(input), [&](int i) { return (db[i].food == query.food); });

    result.clear();
    copy_if(input.begin(), input.end(), back_inserter(result), [&](int i) { return (db[i].score >= query.score); });

    return result.size();
}

vector<int> solution(vector<string> info, vector<string> query)
{
    vector<int> answer;
    vector<Info> db;

    for (string& in : info)
        db.emplace_back(parse(in));

    for (string& q : query)
        answer.emplace_back(filter(db, parse(q)));

    return answer;
}

 

vector로 DB를 구성하는 것은 탐색 시간이 너무 오래 걸린다.

 

그래서 언어, 직군, 경력, 소울푸드 각각을 카테고라이징 하기 위한 무려 4중 중첩 unordered_map을 만들고 점수를 vector로 저장시켰다.

 

그리고는 조건에 해당하는 점수들을 가져오기 위해 4개 조건의 4중 for문을 돌면서 multiset에 점수들을 저장시킨다.

  • 조건이 ANY인 경우에는 모든 후보를 검색하도록 했다.

 

multiset에 저장시킨 점수들을 vector로 변환하여 lower_bound() 함수를 이용해 이진 탐색을 수행한다.

 

하지만, 그래도 시간 초과가 발생했다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <regex>
#include <sstream>
#include <unordered_map>
#include <set>
#include <algorithm>

using namespace std;

enum class LANG   { CPP, JAVA, PYTHON, ANY };
enum class PART   { BACKEND, FRONTEND, ANY };
enum class CAREER { JUNIOR, SENIOR, ANY };
enum class FOOD   { CHICKEN, PIZZA, ANY };

struct Info
{
    LANG lang;
    PART part;
    CAREER career;
    FOOD food;
    int score;
};

Info parse(string& query_string)
{
    Info info;
    istringstream iss(regex_replace(query_string, regex("and"), ""));

    string s;
    int score;

    iss >> s;
    info.lang = (s[0] == 'j') ? LANG::JAVA : (s[0] == 'c') ? LANG::CPP : (s[0] == 'p') ? LANG::PYTHON : LANG::ANY;
    iss >> s;
    info.part = (s[0] == 'b') ? PART::BACKEND : (s[0] == 'f') ? PART::FRONTEND : PART::ANY;
    iss >> s;
    info.career = (s[0] == 'j') ? CAREER::JUNIOR : (s[0] == 's') ? CAREER::SENIOR : CAREER::ANY;
    iss >> s;
    info.food = (s[0] == 'c') ? FOOD::CHICKEN : (s[0] == 'p') ? FOOD::PIZZA : FOOD::ANY;
    iss >> score;
    info.score = score;

    return info;
}

vector<int> solution(vector<string> info, vector<string> query)
{
    vector<int> answer;
    unordered_map<LANG, unordered_map<PART, unordered_map<CAREER, unordered_map<FOOD, vector<int>>>>> db;

    for (string& s : info)
    {
        Info in = parse(s);
        
        db[in.lang][in.part][in.career][in.food].emplace_back(in.score);
    }

    for (string& s : query)
    {
        Info q = parse(s);
        multiset<int> scores;

        vector<LANG> iLang = {q.lang};
        if (q.lang == LANG::ANY) iLang = {LANG::JAVA, LANG::CPP, LANG::PYTHON, LANG::ANY};

        vector<PART> iPart = {q.part};
        if (q.part == PART::ANY) iPart = {PART::BACKEND, PART::FRONTEND, PART::ANY};

        vector<CAREER> iCareer = {q.career};
        if (q.career == CAREER::ANY) iCareer = {CAREER::JUNIOR, CAREER::SENIOR, CAREER::ANY};

        vector<FOOD> iFood = {q.food};
        if (q.food == FOOD::ANY) iFood = {FOOD::CHICKEN, FOOD::PIZZA, FOOD::ANY};

        for (LANG L : iLang) for (PART P : iPart) for (CAREER C : iCareer) for (FOOD F : iFood)
            for (int score : db[L][P][C][F])
                scores.emplace(score);

        vector<int> vScores(scores.begin(), scores.end());

        int nRow = vScores.end() - lower_bound(vScores.begin(), vScores.end(), q.score);
        answer.emplace_back(nRow);
    }

    return answer;
}

 

검색할 때마다 조건에 해당하는 점수들을 가져오지 말고, 입력으로 DB를 구성할 때 조건에 해당하는 곳에 점수를 미리 넣어놓도록 바꿨다.

  • 생각해보니 후보가 ANY가 아닌 경우는 {후보, ANY}로 처리하면 되고, ANY인 경우에는 ANY만 처리하면 된다.

 

하지만, 역시 시간 초과 발생..

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <regex>
#include <sstream>
#include <unordered_map>
#include <set>
#include <algorithm>

using namespace std;

enum class LANG   { CPP, JAVA, PYTHON, ANY };
enum class PART   { BACKEND, FRONTEND, ANY };
enum class CAREER { JUNIOR, SENIOR, ANY };
enum class FOOD   { CHICKEN, PIZZA, ANY };

struct Info
{
    LANG lang;
    PART part;
    CAREER career;
    FOOD food;
    int score;
};

Info parse(string& query_string)
{
    Info info;
    istringstream iss(regex_replace(query_string, regex("and"), ""));

    string s;
    int score;

    iss >> s;
    info.lang = (s[0] == 'j') ? LANG::JAVA : (s[0] == 'c') ? LANG::CPP : (s[0] == 'p') ? LANG::PYTHON : LANG::ANY;
    iss >> s;
    info.part = (s[0] == 'b') ? PART::BACKEND : (s[0] == 'f') ? PART::FRONTEND : PART::ANY;
    iss >> s;
    info.career = (s[0] == 'j') ? CAREER::JUNIOR : (s[0] == 's') ? CAREER::SENIOR : CAREER::ANY;
    iss >> s;
    info.food = (s[0] == 'c') ? FOOD::CHICKEN : (s[0] == 'p') ? FOOD::PIZZA : FOOD::ANY;
    iss >> score;
    info.score = score;

    return info;
}

vector<int> solution(vector<string> info, vector<string> query)
{
    vector<int> answer;
    unordered_map<LANG, unordered_map<PART, unordered_map<CAREER, unordered_map<FOOD, multiset<int>>>>> db;

    for (string& s : info)
    {
        Info in = parse(s);

        vector<LANG> iLang = {LANG::ANY};
        if (in.lang != LANG::ANY) iLang.emplace_back(in.lang);

        vector<PART> iPart = {PART::ANY};
        if (in.part != PART::ANY) iPart.emplace_back(in.part);

        vector<CAREER> iCareer = {CAREER::ANY};
        if (in.career != CAREER::ANY) iCareer.emplace_back(in.career);

        vector<FOOD> iFood = {FOOD::ANY};
        if (in.food != FOOD::ANY) iFood.emplace_back(in.food);

        for (LANG L : iLang) for (PART P : iPart) for (CAREER C : iCareer) for (FOOD F : iFood)
            db[L][P][C][F].emplace(in.score);
    }

    for (string& s : query)
    {
        Info q = parse(s);
        multiset<int>& mset = db[q.lang][q.part][q.career][q.food];
        vector<int> scores(mset.begin(), mset.end());

        int nRow = scores.end() - lower_bound(scores.begin(), scores.end(), q.score);
        answer.emplace_back(nRow);
    }

    return answer;
}

 

4중 중첩 unordered_map에 multiset 대신 vector를 이용해 점수들을 저장한 후 정렬해주니 효율성 2번을 제외하고는 모두 통과되었다.

  • set에 저장하는 것보다 vector에 저장한 후 정렬하는 것이 더 빠르다는 것은 새로 알았다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>
#include <regex>
#include <sstream>
#include <unordered_map>
#include <algorithm>

using namespace std;

enum class LANG   { CPP, JAVA, PYTHON, ANY };
enum class PART   { BACKEND, FRONTEND, ANY };
enum class CAREER { JUNIOR, SENIOR, ANY };
enum class FOOD   { CHICKEN, PIZZA, ANY };

struct Info
{
    LANG lang;
    PART part;
    CAREER career;
    FOOD food;
    int score;
};

Info parse(string& query_string)
{
    Info info;
    istringstream iss(regex_replace(query_string, regex("and"), ""));

    string s;
    int score;

    iss >> s;
    info.lang = (s[0] == 'j') ? LANG::JAVA : (s[0] == 'c') ? LANG::CPP : (s[0] == 'p') ? LANG::PYTHON : LANG::ANY;
    iss >> s;
    info.part = (s[0] == 'b') ? PART::BACKEND : (s[0] == 'f') ? PART::FRONTEND : PART::ANY;
    iss >> s;
    info.career = (s[0] == 'j') ? CAREER::JUNIOR : (s[0] == 's') ? CAREER::SENIOR : CAREER::ANY;
    iss >> s;
    info.food = (s[0] == 'c') ? FOOD::CHICKEN : (s[0] == 'p') ? FOOD::PIZZA : FOOD::ANY;
    iss >> score;
    info.score = score;

    return info;
}

vector<int> solution(vector<string> info, vector<string> query)
{
    vector<int> answer;
    unordered_map<LANG, unordered_map<PART, unordered_map<CAREER, unordered_map<FOOD, vector<int>>>>> db;

    for (string& s : info)
    {
        Info in = parse(s);

        vector<LANG> iLang = {LANG::ANY};
        if (in.lang != LANG::ANY) iLang.emplace_back(in.lang);

        vector<PART> iPart = {PART::ANY};
        if (in.part != PART::ANY) iPart.emplace_back(in.part);

        vector<CAREER> iCareer = {CAREER::ANY};
        if (in.career != CAREER::ANY) iCareer.emplace_back(in.career);

        vector<FOOD> iFood = {FOOD::ANY};
        if (in.food != FOOD::ANY) iFood.emplace_back(in.food);

        for (LANG L : iLang) for (PART P : iPart) for (CAREER C : iCareer) for (FOOD F : iFood)
            db[L][P][C][F].emplace_back(in.score);
    }

    for (auto &L : db) for (auto& P : L.second) for (auto& C : P.second) for (auto& F : C.second)
        sort(F.second.begin(), F.second.end());

    for (string& s : query)
    {
        Info q = parse(s);
        vector<int>& scores = db[q.lang][q.part][q.career][q.food];

        int nRow = scores.end() - lower_bound(scores.begin(), scores.end(), q.score);
        answer.emplace_back(nRow);
    }

    return answer;
}

 

4중 중첩 unordered_map 대신, 4개 조건의 각 후보에 2진수로 겹치지 않는 값을 설정하고, 4개의 조건에 OR 연산을 적용해 하나의 고유값으로 취급하도록 했다.

  • map의 int 키에 이런 식으로 OR 연산을 이용해 처리해 본 적은 처음이다..
  • 중첩 map보다 하나의 map을 사용하는 것이 더 빠르다는 것도 새로 알았다.

 

드디어 정답 처리되었다..

  • 여러 개념들을 잘 활용하고 효율성까지 신경써야 하는 꽤나 어려운 문제였지만 해결하고 나니 뿌듯하다.

 

#include <iostream>
#include <vector>
#include <regex>
#include <sstream>
#include <unordered_map>
#include <algorithm>

using namespace std;

enum class LANG
{
    CPP     = 0b1000000000000,
    JAVA    = 0b0100000000000,
    PYTHON  = 0b0010000000000,
    ANY     = 0b0001000000000
};

enum class PART
{
    BACKEND     = 0b0000100000000,
    FRONTEND    = 0b0000010000000,
    ANY         = 0b0000001000000
};

enum class CAREER
{
    JUNIOR  = 0b0000000100000,
    SENIOR  = 0b0000000010000,
    ANY     = 0b0000000001000
};

enum class FOOD
{
    CHICKEN = 0b0000000000100,
    PIZZA   = 0b0000000000010,
    ANY     = 0b0000000000001
};

struct Info
{
    LANG lang;
    PART part;
    CAREER career;
    FOOD food;
    int score;
};

Info parse(string& query_string)
{
    Info info;
    istringstream iss(regex_replace(query_string, regex("and"), ""));

    string s;
    int score;

    iss >> s;
    info.lang = (s[0] == 'j') ? LANG::JAVA : (s[0] == 'c') ? LANG::CPP : (s[0] == 'p') ? LANG::PYTHON : LANG::ANY;
    iss >> s;
    info.part = (s[0] == 'b') ? PART::BACKEND : (s[0] == 'f') ? PART::FRONTEND : PART::ANY;
    iss >> s;
    info.career = (s[0] == 'j') ? CAREER::JUNIOR : (s[0] == 's') ? CAREER::SENIOR : CAREER::ANY;
    iss >> s;
    info.food = (s[0] == 'c') ? FOOD::CHICKEN : (s[0] == 'p') ? FOOD::PIZZA : FOOD::ANY;
    iss >> score;
    info.score = score;

    return info;
}

vector<int> solution(vector<string> info, vector<string> query)
{
    vector<int> answer;
    unordered_map<int, vector<int>> db;

    for (string& s : info)
    {
        Info in = parse(s);

        vector<LANG> iLang = {LANG::ANY};
        if (in.lang != LANG::ANY) iLang.emplace_back(in.lang);

        vector<PART> iPart = {PART::ANY};
        if (in.part != PART::ANY) iPart.emplace_back(in.part);

        vector<CAREER> iCareer = {CAREER::ANY};
        if (in.career != CAREER::ANY) iCareer.emplace_back(in.career);

        vector<FOOD> iFood = {FOOD::ANY};
        if (in.food != FOOD::ANY) iFood.emplace_back(in.food);

        for (LANG L : iLang) for (PART P : iPart) for (CAREER C : iCareer) for (FOOD F : iFood)
            db[int(L) | int(P) | int(C) | int(F)].emplace_back(in.score);
    }

    for (auto& pr : db)
        sort(pr.second.begin(), pr.second.end());

    for (string& s : query)
    {
        Info q = parse(s);
        vector<int>& scores = db[int(q.lang) | int(q.part) | int(q.career) | int(q.food)];

        int nRow = scores.end() - lower_bound(scores.begin(), scores.end(), q.score);
        answer.emplace_back(nRow);
    }

    return answer;
}
저작자표시 비영리 변경금지

'자료구조 & 알고리즘 > 프로그래머스' 카테고리의 다른 글

Level 2. 숫자 블록  (0) 2023.08.18
Level 2. 요격 시스템  (0) 2023.08.17
Level 2. 디펜스 게임  (0) 2023.08.15
Level 3. 단속카메라  (0) 2023.08.14
Level 3. 입국심사  (0) 2023.08.13
profile

Make Unreal REAL.

@diesuki4

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

검색 태그

티스토리툴바