[C++] level2 순위 검색 67257

참고자료
이 문제는 구글링을 통해 해결하였으므로 참고한 블로그를 상단에 첨부합니다.
https://eunchanee.tistory.com/319
https://transferhwang.tistory.com/442 (비트 연산 이용하신 분! 코드가 더 간단)

📌순위 검색

/* 해당 문제 설명은 링크로 대체한다. */

📌풀이

프로세스

1. info 배열에 각 행(문자열)에서 조건별로 문자열을 트리밍하여 점수로 보관
2. 점수를 기준으로 오름차순 정렬
3. query 배열에 각 행(쿼리열)에서 조건을 나타내는 문자열을 얻어와 이진탐색을 통해 점수와 같은 값 중 가장 첫 번째 위치 값을 가져온다.

0. 필요 변수 초기화

vector<int> answer(query.size(), 0); : query와 동일한 사이즈인 vector, 0으로 초기화(안해두면 값 이상함)
map<string, vector<int>> m; : first는 조건, second는 조건에 해당하는 점수배열 맵
//동일 조건에 여러 사람의 점수가 존재할 수 있으므로 점수 부분은 vector

1. info 배열에 각 행(문자열)에서 조건별로 문자열을 트리밍하여 점수로 보관

vector<vector<string>> str(4, vector<string>(2, "-")); : -로 초기 문자열을 세팅한다.
ex. "javabackendjuniorpizza"가 파싱 결과라면, "-backendjuniorpizza", "--juniorpizza", "---pizza"...
이런 식으로 쿼리에서 나올 수 있는 조건을 모두 map에 담아줄 수 있도록 함

for(int i = 0; i < info.size(); i++){
  string token = "";
  stringstream ss(info[i]); 
  vector<vector<string>> str(4, vector<string>(2, "-")); //4x2짜리 문자열 배열 --언어, 직군, 경력, 소울푸드를 담는 배열
  int index = 0, score = 0;

  //한 개씩 공백을 기준으로 조건을 str에 담음. 점수는 score에
  while(ss >> token){ 
    if(index < 4) //조건
        str[index++][0] = token;
    else //점수
        score = stoi(token);
  }

//점수는 점수대로 보관, 각 조건은 합쳐서 하나의 문자열로
for (int i = 0; i < 2; i++){
  string t1, t2, t3, t4;
  t1 = str[0][i]; //언어
  for (int j = 0; j < 2; j++){
    t2 = str[1][j]; //직군
      for (int k = 0; k < 2; k++){
      t3 = str[2][k]; //경력
        for (int l = 0; l < 2; l++){
        t4 = str[3][l]; //소울푸드
        m[t1 + t2 + t3 + t4].push_back(score);
        }
      }
    }
  }
}

2. 점수를 기준으로 오름차순 정렬

for(auto itr = m.begin(); itr != m.end(); itr++)
    sort(itr->second.begin(), itr->second.end());

• for(auto a : m) 으로 하면 안된다 ...
• 쿼리를 비교할 때 lower_bound()를 이용하여 이진탐색을 진행하려면 반드시 오름차순 정렬 필수

3. query 배열에 각 행(쿼리열)에서 조건을 나타내는 문자열을 얻어와 이진탐색을 통해 점수와 같은 값 중 가장 첫 번째 위치 값을 가져온다.
4. for(int i = 0; i < query.size(); i++){ string str = "", token; stringstream ss(query[i]); int index = 0, score = 0; while(ss >> token){ if(token == "and") continue; //and가 나오면 다음 조건으로 if(index++ < 4) //조건이 4개니까 str += token; else //4이상이라면 마지막 점수 값이 해당되겠지 ? score = stoi(token); } auto itr = lower_bound(m[str].begin(), m[str].end(), score); //이진탐색으로 score와 같거나 큰 반복자 구함 answer[i] = m[str].size() - (itr - m[str].begin()); //실제 인덱스 위치 찾기 위해 m[str].begin() 빼줌 }

📌코드

#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <algorithm>
using namespace std;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer(query.size(), 0); //query와 동일한 사이즈인 vector, 0으로 초기화 //안해두면 값 이상함
    map<string, vector<int>> m; //first : 조건, second : 조건에 해당하는 점수배열 -- 동일 조건에 여러 사람의 점수가 존재할 수 있으므로

    for(int i = 0; i < info.size(); i++){
        string token = "";
        stringstream ss(info[i]); 
        vector<vector<string>> str(4, vector<string>(2, "-")); //4x2짜리 문자열 배열 --언어, 직군, 걍략, 소울푸드를 담는 배열
        int index = 0, score = 0;

        //한 개씩 공백을 기준으로 조건을 str에 담음. 점수는 score에
        while(ss >> token){ 
            if(index < 4)
                str[index++][0] = token;
            else
                score = stoi(token);
        }

        //점수는 점수대로 보관, 각 조건은 합쳐서 하나의 문자열로
        for (int i = 0; i < 2; i++)
        {
            string t1, t2, t3, t4;
            t1 = str[0][i];
            for (int j = 0; j < 2; j++)
            {
                t2 = str[1][j];
                for (int k = 0; k < 2; k++)
                {
                    t3 = str[2][k];
                    for (int l = 0; l < 2; l++)
                    {
                        t4 = str[3][l];
                        m[t1 + t2 + t3 + t4].push_back(score);
                    }
                }
            }
        }
    }

    //점수를 기준으로 오름차순 진행 (lower_bound)을 위해
    for(auto itr = m.begin(); itr != m.end(); itr++)
        sort(itr->second.begin(), itr->second.end());

    //쿼리를 기준으로 분할하여 비교
    for(int i = 0; i < query.size(); i++){
        string str = "", token;
        stringstream ss(query[i]);
        int index = 0, score = 0;

        while(ss >> token){
            if(token == "and") continue; //and가 나오면 다음 조건으로

            if(index++ < 4)
                str += token;
            else
                score = stoi(token);
        }
        auto itr = lower_bound(m[str].begin(), m[str].end(), score); //이진탐색으로 score와 같거나 큰 반복자 구함
        answer[i] = m[str].size() - (itr - m[str].begin()); //실제 인덱스 위치 찾기 위해 m[str].begin() 빼줌
    }

    return answer;
}

---

회고

아직도 한참 멀었다. 진심.
개인적으로 아주 많이 어려웠던 문제였다.
문제 내 조건이 많았고, info에서 조건 별로 끄집어내어 효율적으로 저장하려고 구조체도 만들어보고 배열도 만들어보고 북치고 장구치고 하다가 결국 구글링하여 문제를 풀었다. 개개개개개개ㅐ객어렵고 꼭 더 풀어봐야겠다.

추가로 lower_bound()함수를 통해 이진 탐색을 하는 것을 알게되었다. 대박대박 노션에 정리해두어야지 ....
확실히 머리로 이해하고 넘기는 것보다 구글링을 했더라도 노션에 사용했던 STL 함수나 개념 중 헷갈리거나 완벽히 이해하지 못한 것을 적어두고, 블로그에도 해당 문제에 대해서 정리하면서 복기를 하니 조금은 다음 문제 풀이에 도움이 되는 것 같다.

다 ... 나의 거름이 되..겠지...이...?