https://school.programmers.co.kr/learn/courses/30/lessons/72412
효율성을 떠올리게 만들었던 문제.

문제 설명

문제에서 추출할 수 있는 정보는 다음과 같다.

• Info에서 4개의 범주와 점수가 담긴 문자열이 입력되며, 이를 파싱하여 저장해야 한다.
• Query에서 찾고 싶은 범주와 점수를 담은 질의가 들어오며, 해당 질의를 만족하는 사람 수를 계산해야 한다.
• 질의에 포함된 "-"는 와일드카드이며, 이 조건을 고려하지 않는다(= 조건 따지지 말고 무조건 포함한다)는 의미이다.

해결 과정

크게 문자열 파싱 및 정보 저장, 쿼리 계산 파트로 나눌 수 있다.

문자열 파싱

C++은 split 함수가 없는 대신 stringstream을 통해 공백이 포함된 문자열을 공백 기준으로 파싱할 수 있다.

간단한 사용법은 아래와 같다.
"java backend junior pizza 150"가 입력된다고 가정하자.

    for(int i=0; i<info.size(); i++){
        stringstream ss(info[i]);
        string tmp;
        string now = "";
        int idx = 0;
        while(ss >> tmp){ // 공백 기준으로 잘라 순차적으로 tmp에 담음
            word[idx++] = tmp;
        }

        now = word[0] + word[1] + word[2] + word[3]; // javabackendjuniorpizza
        int num = stoi(word[4]); // 150
        target[now].push_back(num);

        // 추가 코드..

     }

쿼리 계산

각 query마다 4중 for문으로 완전 탐색 시 시간초과가 발생한다.
따라서 query 진입 전 이미 모든 계산이 끝나있어야 한다.

Info에서 하나씩 정보를 추출할 때마다 와일드카드("-")까지 고려하여 한 번에 계산해야 한다.

예를 들어 입력이 "java backend junior pizza 150" 일 경우 "javabackendjuniorpizza" 그룹에 150이 추가되는 것은 당연하고,
와일드카드가 포함된 "-backendjuniorpizza", "--juniorpizza", "java---", "----" 등의 그룹에도 150을 추가해야 한다.

즉 Info[i]에서 추출되는 4개의 카테고리들이 1~4개의 와일드카드로 대체되는 케이스를 모두 찾아야 한다.

백트래킹으로 조합을 구현하면 누락 없이 기존 범주들 중 일부가 와일드카드로 대체된 모든 그룹에 대해서도 동일한 점수를 추가해줄 수 있다.

void dfs(int totalcnt, int nowcnt, int idx, int num){
    if(nowcnt == totalcnt){
        string now = word[0] + word[1] + word[2] + word[3];
        target[now].push_back(num);
    }
    
    for(int i=idx; i<4; i++){
        if(visited[i]) continue;
        visited[i] = true;
        string tmp = word[i];
        word[i] = "-";
        dfs(totalcnt, nowcnt+1, i, num);
        word[i] = tmp;
        visited[i] = false;
    }
}

이를 통해 와일드카드가 포함된 질의가 들어왔을 때 추가적인 계산 없이 바로 정답을 추출할 수 있다.

소스 코드

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

using namespace std;
map<string, vector<int>> target;
map<string, int> m;
string word[5];
bool visited[4];

void dfs(int totalcnt, int nowcnt, int idx, int num){
    if(nowcnt == totalcnt){
        string now = word[0] + word[1] + word[2] + word[3];
        target[now].push_back(num);
    }
    
    for(int i=idx; i<4; i++){
        if(visited[i]) continue;
        visited[i] = true;
        string tmp = word[i];
        word[i] = "-";
        dfs(totalcnt, nowcnt+1, i, num);
        word[i] = tmp;
        visited[i] = false;
    }
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;

    for(int i=0; i<info.size(); i++){
        stringstream ss(info[i]);
        string tmp;
        string now = "";
        int idx = 0;
        while(ss >> tmp){
            word[idx++] = tmp;
        }
        
        now = word[0] + word[1] + word[2] + word[3];
        int num = stoi(word[4]);
        target[now].push_back(num);
        // 와일드카드 -를 반영해야함
        dfs(1, 0, 0, num);
        dfs(2, 0, 0, num);
        dfs(3, 0, 0, num);
        target["----"].push_back(num);
    }
    for(int i=0; i<query.size(); i++){
        stringstream ss(query[i]);
        string tmp;
        string now = "";
        int idx = 0;
        string arr[5];
        while(ss >> tmp){
            if(tmp == "and") continue;
            arr[idx++] = tmp;
        }
        
        now = arr[0] + arr[1] + arr[2] + arr[3];
        int num = stoi(arr[4]);
        int cnt = 0;
        for(auto it: target[now]){
            if(it >= num) cnt++;
        }
        answer.push_back(cnt);
    }
    return answer;
}

교훈

• C++에 없는 Split() 함수의 대용으로 사용할 수 있는 stringstream의 사용법을 익혀두어 시간을 절약하자.