22.05.02. 풀었던 문제들

1. 순위 검색

brute-force하게 풀면 5만 * 10만으로 시간초과가 난다. 따라서 다른 방식으로 풀어야 하는 문제.

먼저 주어지는 조건의 경우의 수는 총 120가지(언어3, 직군2, 경력2, 소울푸드2 + 상관없는 경우의 수 + 1씩 해서 4*3*3*3 = 120이지만 예외처리 귀찮아서 4개짜리 길이의 4진수를 구성했고 string 조건을 숫자로 바꾸어 주는 함수를 만들었다. 그리고 조건은 총 4가지, 한 조건씩 "-"(상관없음)으로 바꾸어 가면 한 사람당 총 16개의 경우의 수가 생긴다. 이를 vector에 push한다. 그러면 vector[i]는 조건이 i에 해당하는 사람들의 점수 list가 되고, list를 sort해 두면 binary search할 수 있다.

이어서, query의 조건도 숫자로 바꾸어서 vector[i]에 있는 list를 탐색하고, 이를 binary search(lower bound)해서 나오는 iterator와 vector.end()를 빼서 사람 수를 구할 수 있다. 시간복잡도는 10만 * log(5만)이므로 150만 정도로, 충분히 시간 내에 풀린다.

binary search는 접근도 못했다. 아직 많이 미숙하다. 그리고 모범답안을 보면서 더 부족하단 것을 많이 느꼈다. 조건을 굳이 숫자로 바꿀 필요가 없는게, map<string, vector<int>>을 사용해 버리고 string을 다뤄주면 매번 vector<string>의 백업본을 불러올 필요 없이, 조건에 해당하면 "-"를 string에 넣어버리면 된다..... 분발하자!

// 순위 검색
 
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
// 조건을 4진수로 바꿔주는 함수.
// 언어 : 1의자리. cpp - 1, java - 2, python - 3, - - 0
// 직군 : 2번째 자리. backend - 1, frontend - 2, - - 0
// 경력 : 3번째 자리. junior - 1, senior - 2, - - 0
// 소울푸드 : 4번째 자리. chicken - 1, pizza - 2, - - 0
// ex. java backend junior pizza : 2112 -> 2 + 4 + 16 + 128 = 150
int conditionToNum(vector<string> v){
    int digit = 1, result = 0;
    string s;
    for(int i = 0; i<v.size(); i++){
        s = v[i];
        if(s == "-") result += digit * 0;
        else if(s == "cpp" || s == "backend" || s == "junior" || s == "chicken") result += digit*1;
        else if(s == "java" || s == "frontend" || s == "senior" || s == "pizza") result += digit*2;
        else if(s == "python") result += digit*3;
        digit *= 4;
    }
    return result;
}
 
vector<int> changeCondition(vector<string> v){
    vector<string> cases = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
                     "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
    vector<string> backup(v.begin(), v.end());
    vector<int> result;
    for(string c : cases){
        for(int i = 0; i<4; i++){
            v[i] = backup[i];
        }
        
        for(int i = 0; i<4; i++){
            if(c[i] == '1'){
                v[i] = "-";
            }
        }
        
        result.push_back(conditionToNum(v));
    }
    
    return result;
}
 
vector<int> solution(vector<string> info, vector<string> query) {    
    int num_cases = 256;
    istringstream iss; string buffer;
    vector<vector<int>> point_vector(num_cases); // point_vector[i] : 조건이 i인 사람들의 점수
    for(string s : info){
        iss.clear(); iss.str(s);
        vector<string> data;
        while(getline(iss, buffer, ' ')){
            data.push_back(buffer);
        } data.pop_back();
        
        vector<int> all_cases = changeCondition(data);
        for(int c : all_cases){
            point_vector[c].push_back(stoi(buffer));
        }
    }
    
    for(vector<int> &v : point_vector){
        sort(v.begin(), v.end());
    }
    
    vector<int> answer;
    vector<int>::iterator iter;
    for(string s : query){
        iss.clear(); iss.str(s);
        vector<string> question;
        while(getline(iss, buffer, ' ')){
            if(buffer == "and") continue;
            question.push_back(buffer);
        } question.pop_back();
        
        vector<int> target = point_vector[conditionToNum(question)];
        iter = lower_bound(target.begin(), target.end(), stoi(buffer));
        answer.push_back(target.end() - iter);
    }
    
    return answer;
}
 
// simple하게 푼다면, 50,000 * 100,000 = 5,000,000,000 (50억)이므로 시간 초과임.
// nlogn으로 풀어라는 문제이다.

 

 

2. k진수에서 소수 개수 구하기

진수 변환하고 -> 0으로 string parsing(이 때, buffer에 아무것도 없는 경우 stoi가 되지 않으므로 buffer==""일 때 검사 필요), 이후 숫자들이 소수인지 판정하면 됨. 다만, 이 경우 숫자가 매우 커질 수 있기 때문에 체를 사용하면 메모리 초과가 날 수 있음. 따라서 각 수에 대해 판정하면 될 것.