[c++] 2019 카카오 개발자 겨울 인턴십 :: 불량 사용자

문제

불량 사용자 문제 바로가기

코딩테스트 연습 - 불량 사용자

 

풀이

처음에는 제재 아이디 당 몇 가지의 경우의 수가 가능한 지 계산하려고 했으나, 이렇게 한다면 기존에 제재 아이디에 걸린 아이디는 다시금 판단하면 안되는 등 생각해야 할 문제가 많아지므로 아래의 방법을 사용한다.

제재 아이디와 매칭되는 아이디를 찾을때마다 dfs로 돌면서 모든 제재 아이디에 매칭되는 경우의 수를 찾으면 된다. 입력의 범위가 작아서 시간복잡도는 문제 없다. 더해서 순열이 아니라 조합이므로 순서에 관계없이 하나의 경우로 치부해야 한다는 걸 명심하자!

 

 

코드

#include <string>
#include <vector>
#include <regex>
#include <algorithm>
#include <unordered_set>

using namespace std;

vector<string> bannedIdList;
unordered_set<int> answer;
unordered_map<string, int> mappedList;
int powList[8] = {1,2,4,8,16,32,64,128};

string convertBannedId(string bannedId){
    auto foundIdx = bannedId.find("*");
    while(foundIdx != string::npos){
        bannedId[foundIdx] = '.';
        foundIdx = bannedId.find("*");
    }
    return bannedId;
}

void dfs(vector<string>& userIdList, int bannedIdx, int bitSum){
    if(bannedIdx == bannedIdList.size()){ // 모든 제재 아이디 검사 완료
        answer.insert(bitSum); // 완료한 bitSum 저장 (순서 바뀌어도 같은 경우 체크 가능)
        return;
    }
    
    string bannedId = bannedIdList[bannedIdx];
    regex re(bannedId);
    
    for(int i=0; i<userIdList.size(); i++){
        if(regex_match(userIdList[i], re)){ // 제재 아이디에 해당한다면
            string tmp = userIdList[i];  
            userIdList.erase(userIdList.begin()+i); // 해당 아이디를 제외하고
            dfs(userIdList, bannedIdx + 1, bitSum + mappedList[tmp]); // 다음 제재 아이디 추적
            userIdList.insert(userIdList.begin() + i, tmp);
        }
    }
}

int solution(vector<string> userIdList, vector<string> banned_id_list) {
    for(int i=0; i<banned_id_list.size(); i++){ // 주어진 리스트 * => .로 변경하여 regex쓸 수 있게 하기
        bannedIdList.push_back(convertBannedId(banned_id_list[i]));
    }
    for(int i=0; i<userIdList.size(); i++){ // userId와 2의 진수들 매핑
        mappedList[userIdList[i]] = powList[i];
    }
    dfs(userIdList, 0, 0);
    
    return answer.size();
}

 

결과

테스트 1 〉	통과 (0.02ms, 4.32MB)
테스트 2 〉	통과 (0.05ms, 3.71MB)
테스트 3 〉	통과 (0.04ms, 3.72MB)
테스트 4 〉	통과 (0.05ms, 4.32MB)
테스트 5 〉	통과 (101.91ms, 4.27MB)
테스트 6 〉	통과 (0.96ms, 4.33MB)
테스트 7 〉	통과 (0.05ms, 4.26MB)
테스트 8 〉	통과 (0.06ms, 4.33MB)
테스트 9 〉	통과 (0.06ms, 4.27MB)
테스트 10 〉	통과 (0.05ms, 4.27MB)
테스트 11 〉	통과 (0.07ms, 3.84MB)