[프로그래머스] 불량 사용자

2019 카카오 개발자 겨울 인턴십 - 불량 사용자

풀이

[제한사항] 부분을 보면 user_id와 banned_id의 배열의 크기가 8이하 이다. 그냥 하나씩 비교해도 문제 없을거라고 생각하고 vector와 set을 이용해서 문제를 풀었다
첫 번째 입출력 예시로 문제 푼 방법을 적어보자

그리고 백트레킹으로 목록을 set에 담아두고 모든 경우의 set들을 final_check 벡터에 저장했다.

다른 방법

방문 여부를 확인하여 푸는 방법도 있다. 다음에 이런 비슷한 유형이 나오면 두가지 방법 모두 떠올려야겠다.

반성

※ 모든 문제들은 내가 그동안 풀었던 방법으로 풀 수 있다.
※ 문제를 처음부터 끝까지 차분하게 쭉 읽어보자(제한사항 등)

카카오 기술 블로그에서 알려주는 방법!

제한사항이 비교적 작으므로, 가능한 모든 방법을 시도해 보는 방식으로 문제를 해결할 수 있습니다. 응모자 아이디 목록의 길이가 N, 불량 사용자 아이디 목록의 길이가 K 일 때, 응모자 아이디 N개 중 K개를 선택하는 모든 방법을 시도해 봅니다. 선택된 아이디 목록이 불량 사용자 목록으로 매핑될 수 있다면 카운트를 하나 증가시킵니다. 최종적으로 매핑에 성공한 횟수를 반환하면 됩니다.

코드

#include <string>
#include <vector>
#include <set>
using namespace std;

vector<set<int>> final_check;
set<int> tmp;

void dfs(int depth, int limit, vector<vector<int>> &arr){
    if(depth == limit){
    	// tmp에 저장된 목록이 이미 final_check 벡터에 들어있다면 그냥 return 해준다
        for(auto &it : final_check) if(it == tmp) return;
        final_check.push_back(tmp);
        return;
    }
    for(auto &it : arr[depth]){
        if(tmp.find(it) != tmp.end()) continue; // set안에 있다는 뜻이므로 그냥 넘어간다
        tmp.insert(it);
        dfs(depth+1, limit, arr);
        tmp.erase(it);
    }
}
int solution(vector<string> user_id, vector<string> banned_id) {
    int user_len = (int)user_id.size();
    int ban_len = (int)banned_id.size();
    
    vector<vector<int>> check;
    check.resize(ban_len);
    // user_id와 banned_id를 비교해준다
    for(int i = 0 ; i < ban_len ; i++){
        for(int j = 0 ; j < user_len ; j++){
            if(banned_id[i].size() != user_id[j].size()) continue;
            //
            bool same = true;
            for(int k = 0 ; k < banned_id[i].size() ; k++){
                if(banned_id[i][k] == '*') continue;
                if(banned_id[i][k] != user_id[j][k]) same = false;
            }
            //
            if(same) check[i].push_back(j);
        }
    }
    dfs(0, ban_len, check);
    return (int)final_check.size();
}