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

프로그래머스

 

info와, query를 잘라 각각 users와 conditions에 담은 다음

user마다 조건을 체크하면 되지 않을까?

#include <string>
#include <vector>
#include <sstream>

using namespace std;

vector<vector<string>> users;
vector<vector<string>> conditions;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    // info 문자열 분리
    for(int i = 0; i < info.size(); i++) {
        istringstream iss(info[i]);
        string token;
        vector<string> tokens;
        
        while (getline(iss, token, ' '))
            tokens.push_back(token);
        
        users.push_back(tokens);
    }
    
    // query 문자열 분리
    for(int i = 0; i < query.size(); i++) {
        istringstream iss(query[i]);
        string token;
        vector<string> tokens;
        
        while (getline(iss, token, ' ')) {
            if (token != "and") {
                tokens.push_back(token);
            }
        }
        
        condition.push_back(token);
    }
    
    // 각 조건마다 조건을 충족하는 유저의 수를 확인
    for(int i = 0; i < conditions.size(); i++) {
        // 이거 최악 50000 x 100000이면 시간 초과날거 같은데?
    }
    
    return answer;
}

 

 

작성하다가 중간에 딱봐도 시간초과 날 거 같아서 갈아치웠다

 

• 그래서 떠오른게 map을 이용해서 특정 조건을 key로 가지는 경우 해당 맵의 value에 그 인원의 점수를 추가 한 뒤
  이후 query를 돌며 각 조건마다 value 벡터에 들어있는 점수가 X점 이상인지 체크하도록 하는 것
• 여기서 query의 조건이 -면 해당 조건을 고려하지 않는 것이므로 어느 문자열이 들어가도 상관없기 때문에
  예를 들어 info의 조건이 java backend junior pizza라면 각 조건들이 -가 될 수 있는 것도 고려해야함

 

#include <string>
#include <vector>
#include <sstream>
#include <unordered_map>

using namespace std;

unordered_map<string, vector<int>> m;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    string s[4], score = "";
    
    // info 문자열을 분리
    for(int i = 0; i < info.size(); i++) {
        istringstream iss(info[i]);
        iss >> s[0] >> s[1] >> s[2] >> s[3] >> score;
        
        // 분리된 문자열을 key로 가지는 value 배열에 점수 추가
        // 단 각 조건마다 -이 될 때를 문자열을 key로 가지는 value 배열에도 점수 추가해주어야함
        // 4개의 조건이 각각 info의 조건 또는 -가 될 수 있으므로 점수를 추가해주어야하는 key는 총 16가지
        for(int j = 0; j < 16; j++) {
            string key = "";
            int num = j;
            
            // num % 2 == 0은 -가 되는 경우
            // 0000, 0001, 0010, 0011...
            // 비트마스크를 이용해 조합을 만들어도 될 듯
            for(int k = 0; k <= 3; k++) {
                if(num % 2 == 0)
                    key += "-";
                else
                    key += s[k];
                
                num /= 2;
            }
            
            // unordered_map에 삽입
            m[key].push_back(stoi(score));
        }
    }
    
    // key값의 value에 조건을 충족하는 인원이 몇 명인지 체크
    for(int i = 0; i < query.size(); i++) {
        // 조건을 충족하는 인원 수
        int cnt = 0;
        
        // 조건 문자열 자르기, and 무시 필요
        istringstream iss(query[i]);
        iss >> s[0] >> score >> s[1] >> score >> s[2] >> score >> s[3] >> score;
        
        // key 생성
        string key = s[0] + s[1] + s[2] + s[3];
        // key에 해당하는 value 배열 받아오기
        vector<int> scores = m[key];
        
        // 점수 조건 
        int con = stoi(score);
        
        // scores 배열에서 조건을 충족하는지 체크
        for(int j = 0; j < scores.size(); j++)
            // 충족하면 ++
            if(scores[j] >= con) 
                cnt++;
        
        // 조건을 충족하는 인원 수 저장
        answer.push_back(cnt);
    }
    
    return answer;
}