[프로그래머스/C++] 순위 검색

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

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

순위 검색

문제

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• info 배열의 크기는 1 이상 50,000 이하입니다.
• info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
  • 개발언어는 cpp, java, python 중 하나입니다.
  • 직군은 backend, frontend 중 하나입니다.
  • 경력은 junior, senior 중 하나입니다.
  • 소울푸드는 chicken, pizza 중 하나입니다.
  • 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
• query 배열의 크기는 1 이상 100,000 이하입니다.
• query의 각 문자열은 "[조건] X" 형식입니다.
  • [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
  • 언어는 cpp, java, python, - 중 하나입니다.
  • 직군은 backend, frontend, - 중 하나입니다.
  • 경력은 junior, senior, - 중 하나입니다.
  • 소울푸드는 chicken, pizza, - 중 하나입니다.
  • '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
  • X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
  • 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

 

풀이

입출력 예시

 

풀이

문제 설명은 정말 긴데, 읽으면 읽을수록 점점 재미있어 졌다.

지원자 정보 부터 담아보도록 하자. 지원자 정보는 구조체로, 지원자들 목록은 벡터를 이용했다. 이름하여 구조체 벡터.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct jiwonja_jeongbo {
    string lang;
    string group;
    string career;
    string food;
    int score;
}jj;

---

처음에 공백(" ")단위로 잘라서 지원자 정보에 담아, 벡터에 저장해준다. info와 query에서 자르는 기준이 조금 다른 점을 신경써주면 조건을 얻는 것도 끝이었다.

조건에 해당하는 부분들도 지원자 정보와 동일하다. 그러니 마찬가지로 위 과정을 반복해주면 조건에 대한 벡터도 얻을 수 있다.

 

void input_info(vector<string> jj_info_query, vector<jj>& jjlist, string gijun) {
    jj jiwonja; // 지원자 정보와 조건 정보를 담을 임시 변수
    size_t pos; // 기준 위치
    string tmp;

    for (auto& i : jj_info_query) {
        tmp = i;

        // 언어
        pos = tmp.find(gijun);
        jiwonja.lang = tmp.substr(0, pos);
        tmp = tmp.substr(pos + gijun.length());

        // 직군
        pos = tmp.find(gijun);
        jiwonja.group = tmp.substr(0, pos);
        tmp = tmp.substr(pos + gijun.length());

        // 경력
        pos = tmp.find(gijun);
        jiwonja.career = tmp.substr(0, pos);
        tmp = tmp.substr(pos + gijun.length());

        // 쏘울 푸드
        pos = tmp.find(" "); // 숫자 직전 부분은 항상 공백만 존재
        jiwonja.food = tmp.substr(0, pos);
        tmp = tmp.substr(pos + 1);

        // 점수
        jiwonja.score = stoi(tmp);

        jjlist.push_back(jiwonja);
    }
}

---

이제, 조건을 비교하면서 조건에 해당되는 사람이 몇 명인지를 찾아야한다. "-"일 경우에는 조건을 고려하지 않으므로 모든 지원자가 해당된다.

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    vector<jj> jiwonja_list; // 지원자 목록
    vector<jj> jogeon_list; // 조건 목록
    int count = 0;
    
    input_info(info, jiwonja_list, " ");
    input_info(query, jogeon_list, " and ");
    
    for (const auto& jogeon : jogeon_list) {
        count = 0;
        for (const auto& jiwonja : jiwonja_list) {
            if (jogeon.lang == jiwonja.lang || jogeon.lang == "-") {
                if (jogeon.group == jiwonja.group || jogeon.group == "-") {
                    if (jogeon.career == jiwonja.career || jogeon.career == "-") {
                        if (jogeon.food == jiwonja.food || jogeon.food == "-") {
                            if (jogeon.score <= jiwonja.score) {
                                count++;
                            }
                        }
                    }
                }
            }
        }
        answer.push_back(count);
    }

    return answer;
}

---

하지만 효율성에서 시원하게 말아먹었다.

마지막 비교를 하는 과정에 2중 for문이 들어가는데 여기가 문제인 것 같았다. 비교를 하는 다른 방법을 생각해봐야 한다. 고민을 계속 해봤지만 여전히 효율성은 통과되질 않는다. 방식 자체를 바꿔야하는 것 같았다.

 

조금 힌트를 얻고자 서칭을 돌려봤다. 나는 이 놀라운 힌트를 보고 바로 머리가 돌아가기 시작했다. 힌트는 같은 조합의 경우끼리 뭉쳐 그룹으로 나누는 것이었다.

 

깔끔하게 초기화를 누르자. 신문물(?)인 sstream을 이용해서 문자열을 분할시켜서 조합을 통해 맵을 만들자. 맵은 그룹을 key로, 코딩 테스트 점수들을 value로 가진다.

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

using namespace std;

map<string,vector<int>> input_info(vector<string> info_query) {
    vector<int> comb;
    map<string, vector<int>> info_map;
    string group = "";
    int score;

    for (auto& info : info_query) {
        vector<string> jeongbo(4);
        stringstream ss(info);
        for (int i = 0; i < 4; i++) {
            ss >> jeongbo[i];
        }
        ss >> score;

        for (int i = 0; i <= 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (j < i) {
                    comb.push_back(0);
                }
                else {
                    comb.push_back(1);
                }
            }
            do { // 그룹 조합 생성
                group = "";
                for (int i = 0; i < comb.size(); i++) {
                    if (comb[i] == 0) {
                        group += "-";
                    }
                    else {
                        group += jeongbo[i];
                    }
                }
                if (info_map.count(group)) {
                    info_map[group].push_back(score);
                }
                else {
                    info_map.insert({ group, { score } });
                }
            } while (next_permutation(comb.begin(), comb.end()));
            comb.clear();
        }
    }

    return info_map;
}

---

비교만 해주면 끝이 난다. 비교는 맵에다가 그룹들을 저장시켰다. 해당하는 조건에 맞는 그룹을 찾아서 코딩 테스트 점수만 찾아서 비교하면 된다. 여기서 또 효율성이 걸릴 수 있으니 이진 탐색을 사용해보자. 그러기 위해서 지원자 맵을 정렬해주는 사전 작업이 필요하다.

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    map<string, vector<int>> jiwonja_map = input_info(info);

    for (auto& j : jiwonja_map) {
        sort(j.second.begin(), j.second.end());
    }

    return answer;
}

---

이어서 query에 있는 정보들도 분할해서 가져온 뒤, 조건에 맞는 그룹의 값(= 점수 벡터)를 가져온다. 이제, 이진 탐색으로 점수를 찾기만 하면 끝.

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    map<string, vector<int>> jiwonja_map = input_info(info);

    for (auto& jiwonja : jiwonja_map) {
        sort(jiwonja.second.begin(), jiwonja.second.end());
    }

    for (auto& q : query) {
        string jogeon = "";
        vector<string> jeongbo(4);
        stringstream ss(q);
        vector<int> score_list;
        int score;
        for (int i = 0; i < 4; i++) {
            ss >> jeongbo[i];
            if (jeongbo[i] == "and") {
                i--;
            }
            else {
                jogeon += jeongbo[i];
            }
        }
        ss >> score;

        score_list = jiwonja_map[jogeon];
        answer.push_back(score_list.size() - (lower_bound(score_list.begin(), score_list.end(), score) - score_list.begin()));
    }

    return answer;
}

lower_bound()는 이진탐색을 통해 찾는 값 보다 크거나 같은 원소의 위치를 반환한다.

인덱스를 얻고 싶다면 해당 값에 begin()을 빼주면 얻을 수 있다.

 

위 코드에서 size에서 인덱스를 뺀 이유는 한 그룹에 속한 사람이 5명이고 성적이 { 50, 60, 70, 80, 90 } 이라고 할 때, 60점 이상인 사람들은 4명이다. 이는 60점의 전체 크기인 5에서 인덱스 1번을 뺀 것과 같기 때문이다.

---

전체 코드

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

using namespace std;

map<string,vector<int>> input_info(vector<string> info_query) {
    vector<int> comb;
    map<string, vector<int>> info_map;
    string group = "";
    int score;

    for (auto& info : info_query) {
        vector<string> jeongbo(4);
        stringstream ss(info);
        for (int i = 0; i < 4; i++) {
            ss >> jeongbo[i];
        }
        ss >> score;

        for (int i = 0; i <= 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (j < i) {
                    comb.push_back(0);
                }
                else {
                    comb.push_back(1);
                }
            }
            do { // 그룹 조합 생성
                group = "";
                for (int i = 0; i < comb.size(); i++) {
                    if (comb[i] == 0) {
                        group += "-";
                    }
                    else {
                        group += jeongbo[i];
                    }
                }
                if (info_map.count(group)) {
                    info_map[group].push_back(score);
                }
                else {
                    info_map.insert({ group, { score } });
                }
            } while (next_permutation(comb.begin(), comb.end()));
            comb.clear();
        }
    }

    return info_map;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    map<string, vector<int>> jiwonja_map = input_info(info);

    for (auto& jiwonja : jiwonja_map) {
        sort(jiwonja.second.begin(), jiwonja.second.end());
    }

    for (auto& q : query) {
        string jogeon = "";
        vector<string> jeongbo(4);
        stringstream ss(q);
        vector<int> score_list;
        int score;
        for (int i = 0; i < 4; i++) {
            ss >> jeongbo[i];
            if (jeongbo[i] == "and") {
                i--;
            }
            else {
                jogeon += jeongbo[i];
            }
        }
        ss >> score;

        score_list = jiwonja_map[jogeon];
        answer.push_back(score_list.size() - (lower_bound(score_list.begin(), score_list.end(), score) - score_list.begin()));
    }

    return answer;
}

혹시 몰라 남기는 효율성 말아먹은 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct jiwonja_jeongbo {
    string lang;
    string group;
    string career;
    string food;
    int score;
}jj;

void input_info(vector<string> jj_info_query, vector<jj>& jjlist, string gijun, int min_score) {
    jj jiwonja; // 지원자 정보와 조건 정보를 담을 임시 변수
    size_t pos; // 기준 위치
    string tmp;

    for (auto& i : jj_info_query) {
        tmp = i;

        // 언어
        pos = tmp.find(gijun);
        jiwonja.lang = tmp.substr(0, pos);
        tmp = tmp.substr(pos + gijun.length());

        // 직군
        pos = tmp.find(gijun);
        jiwonja.group = tmp.substr(0, pos);
        tmp = tmp.substr(pos + gijun.length());

        // 경력
        pos = tmp.find(gijun);
        jiwonja.career = tmp.substr(0, pos);
        tmp = tmp.substr(pos + gijun.length());

        // 쏘울 푸드
        pos = tmp.find(" "); // 숫자 직전 부분은 항상 공백만 존재
        jiwonja.food = tmp.substr(0, pos);
        tmp = tmp.substr(pos + 1);

        // 점수
        jiwonja.score = stoi(tmp);

        // 최소 코딩 테스트 점수를 넘긴 사람만 추가
        if (jiwonja.score >= min_score) {
            jjlist.push_back(jiwonja);
        }
    }
}

bool cmp(jj a, jj b) { return a.score < b.score; }

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    vector<jj> jiwonja_list; // 지원자 목록
    vector<jj> jogeon_list; // 조건 목록
    int count;
    jj min_score;

    input_info(query, jogeon_list, " and ", 0);
    min_score = *min_element(jogeon_list.begin(), jogeon_list.end(), cmp);
    input_info(info, jiwonja_list, " ", min_score.score);
    
    for (const auto& jogeon : jogeon_list) {
        count = 0;
        for (const auto& jiwonja : jiwonja_list) {
            if (jogeon.lang == jiwonja.lang || jogeon.lang == "-") {
                if (jogeon.group == jiwonja.group || jogeon.group == "-") {
                    if (jogeon.career == jiwonja.career || jogeon.career == "-") {
                        if (jogeon.food == jiwonja.food || jogeon.food == "-") {
                            if (jogeon.score <= jiwonja.score) {
                                count++;
                            }
                        }
                    }
                }
            }
        }
        answer.push_back(count);
    }

    return answer;
}

 

결과