순위 검색(31분: 40점)

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

구현 아이디어 8분 구현 23분

풀이(효율성 테스트 실패)

정확성 테스트는 통과했는데 효율성 테스트가 실패했다. 효율성이 중요한 문제였는지 정확성 테스트 케이스가 18개, 효율성 테스트 케이스가 4개인데 정확성 테스트를 다 통과하고 40점을 받았다.

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

// 지원자들은 info에 있는 모든 항목을 기재한다.
// 개발팀은 점수를 제외하고 고려하는 정도가 각각 다르다.

// map에 점수를 추가할 때 개발팀에서 나올 수 있는 모든 경우의 수를 key로 저장한다.
// 예: "java backend junior pizza 150"의 경우
// m[----].push_back(150);
// m[java---].push_back(150);
// m[-backend--].push_back(150);
// ...

using namespace std;

int check[4];
map<string, vector<int>> m;

void DFS(int L, int i, int e, const string& info)
{
    if(L == e)
    {
        // 디버깅.
        //for(auto it : check)
            //printf("%d ", it);
        
        //printf("\n");
        
        stringstream ss(info);
        string a[5];
        ss >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
        
        string result;
        for(int i = 0; i < 4; ++i)
        {
            if(check[i])
                result += a[i];
            else result += "-";
        }
        
        m[result].push_back(stoi(a[4]));
    }
    else
    {
        for(; i < 4; ++i)
        {
            if(check[i] == 0)
            {
                check[i] = 1;
                DFS(L + 1, i + 1, e, info);
                check[i] = 0;
            }
        }
    }
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    int N = info.size();
    for(int i = 0; i < N; ++i)
        for(int j = -1; j < 4; ++j) DFS(0, 0, j + 1, info[i]);
    
    for(int i = 0; i < query.size(); ++i)
    {
        int sum = 0;
        
        stringstream ss(query[i]);
        string a[8];
        ss >> a[0] >> a[1] >> a[2] >> a[3] >> a[4] >> a[5] >> a[6] >> a[7];
        string result = a[0] + a[2] + a[4] + a[6];
        
        for(auto& it : m[result])
        {
            if(it >= stoi(a[7]))
                ++sum;
        }
        
        answer.push_back(sum);
    }
    
    return answer;
}

---

풀이(효율성 테스트 실패)

재귀가 문제일까하는 마음에 일일이 m에 key와 value를 넣었다만 40점...

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

using namespace std;

int check[4];
map<string, vector<int>> m;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    int N = info.size();
    for(int i = 0; i < N; ++i)
    {
        stringstream ss(info[i]);
        string a[5];
        ss >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
        int score = stoi(a[4]);
        
         m["----"].push_back(score);
        
         m[a[0] + "---"].push_back(score);
         m["-" + a[1] + "--"].push_back(score);
         m["--" + a[2] + "-"].push_back(score);
         m["---" + a[3]].push_back(score);
        
         m[a[0] + a[1] + "--"].push_back(score);
         m[a[0] + "-" + a[2] + "-"].push_back(score);
         m[a[0] + "--" + a[3]].push_back(score);
        
         m["-" + a[1] + a[2] + "-"].push_back(score);
         m["-" + a[1] + "-" + a[3]].push_back(score);
         m["--" + a[2] + a[3]].push_back(score);
        
         m[a[0] + a[1] + a[2] + "-"].push_back(score);
         m[a[0] + a[1] + "-" + a[3]].push_back(score);
         m[a[0] + "-" + a[2] + a[3]].push_back(score);
         m["-" + a[1] + a[2] + a[3]].push_back(score);
        
         m[a[0] + a[1] + a[2] + a[3]].push_back(score);
    }
    
    for(int i = 0; i < query.size(); ++i)
    {
        int sum = 0;
        
        stringstream ss(query[i]);
        string b[8];
        ss >> b[0] >> b[1] >> b[2] >> b[3] >> b[4] >> b[5] >> b[6] >> b[7];
        string result = b[0] + b[2] + b[4] + b[6];
        
        for(auto& it : m[result])
            if(it >= stoi(b[7]))
                ++sum;
        
        answer.push_back(sum);
    }
    
    return answer;
}

---

풀이

sum을 구할 때 if(it >= stoi(b[7]))에 있는 stoi(b[7])을 미리 int 형변환하여 채점하니 통과했다. 이런 작은 부분들을 꼭 챙기자.

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

using namespace std;

int check[4];
map<string, vector<int>> m;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    int N = info.size();
    for(int i = 0; i < N; ++i)
    {
        stringstream ss(info[i]);
        string a[5];
        ss >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
        int score = stoi(a[4]);
        
         m["----"].push_back(score);
        
         m[a[0] + "---"].push_back(score);
         m["-" + a[1] + "--"].push_back(score);
         m["--" + a[2] + "-"].push_back(score);
         m["---" + a[3]].push_back(score);
        
         m[a[0] + a[1] + "--"].push_back(score);
         m[a[0] + "-" + a[2] + "-"].push_back(score);
         m[a[0] + "--" + a[3]].push_back(score);
        
         m["-" + a[1] + a[2] + "-"].push_back(score);
         m["-" + a[1] + "-" + a[3]].push_back(score);
         m["--" + a[2] + a[3]].push_back(score);
        
         m[a[0] + a[1] + a[2] + "-"].push_back(score);
         m[a[0] + a[1] + "-" + a[3]].push_back(score);
         m[a[0] + "-" + a[2] + a[3]].push_back(score);
         m["-" + a[1] + a[2] + a[3]].push_back(score);
        
         m[a[0] + a[1] + a[2] + a[3]].push_back(score);
    }
    
    for(int i = 0; i < query.size(); ++i)
    {
        int sum = 0;
        
        stringstream ss(query[i]);
        string b[8];
        ss >> b[0] >> b[1] >> b[2] >> b[3] >> b[4] >> b[5] >> b[6] >> b[7];
        string result = b[0] + b[2] + b[4] + b[6];
        
        int score = stoi(b[7]);
        
        for(auto& it : m[result])
            if(it >= score)
                ++sum;
        
        answer.push_back(sum);
    }
    
    return answer;
}

---

재귀 풀이에도 똑같이 적용하니 통과는 했다. 다만 시간 차이가 2배쯤 났다. 함수 콜은 비용이 많이 필요한 작업이란 걸 다시금 체득했다.