[2019 카카오 개발자 겨울 인턴십] 불량 사용자 (lv3)

 

https://programmers.co.kr/learn/courses/30/lessons/64064

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

 

[풀이 방법]

이 문제는 중복을 허용하지 않는 조합에 관한 문제이다.

 

1. 질문을 하나씩 돌면서 체크가 안되어있고 질문과 일치하는 단어를 체크한다.

2. 모든 문제를 다 돌았다면 체크된 단어들을 저장한다.

3. 모든 경우를 다 체크했다면 저장된 결과들을 중복 제거한다.

4. 중복제거해서 남은 결과의 갯수가 answer 이다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

vector <string> v;
map <string, bool> m; 
int answer = 0;
vector <string> res;

bool check(string user, string q) {
    if(user.size() != q.size())
        return false;
    
    for(int i=0; i<q.size(); i++) {
        if(q[i] == '*') continue;
        if(q[i] != user[i])
            return false;
    }
    return true;
}

void dfs(int cnt, int N) {
    if(cnt == N) {
       string tmp = "";
        for(auto user: m) {
            if(user.second)
                tmp += user.first;
        }
        res.push_back(tmp);
      
        return;
    }
    for(auto user: m) {
        // 이미 체크되었다면 패스
        if(user.second) continue;
        // 해당된다면
        if(check(user.first, v[cnt])) {
            m[user.first] = true;
            dfs(cnt+1, N);
            m[user.first] = false;
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    
    for(auto user: user_id)
        m.insert({user, false});
    
    v = banned_id;
    
    dfs(0, banned_id.size());
    
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    
    answer = res.size();
    return answer;
}

(후기)

굳이 map 을 사용했어야 했나 싶다.