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

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

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

1. 각 금지 아이디가 가질 수 있는 유저아이디 구하기.

2. 동일한 단어가 포함되지 않는 순열 생성.

3. 해당 순열로 부터 순서의 바꿈으로 만들어 지는 중복 제거 => 정렬 후 체크

 

 

#include <string>
#include <vector>
#include<iostream>
#include<map>
using namespace std;
map<string, bool> m[8];
map<string, bool> common;
map<string, bool> check_m;
vector<string> list;
vector<string> res;
vector<string> check_v;
bool visit[8];
bool check_visit[8];
int answer = 0;

bool check_fl = true;

void check()
{
    if (!check_fl)
    {
        return;
    }

    if (check_v.size() == res.size())
    {
        string str = "";
        for (int i = 0; i < check_v.size(); i++)
        {
            str += check_v[i] + " ";
        }
        if (check_m[str])
        {
            check_fl = false;
            return;
        }
    }

    for (int i = 0; i < res.size(); i++)
    {
        if (!check_visit[i])
        {
            check_visit[i] = true;
            check_v.push_back(res[i]);
            check();
            check_v.pop_back();
            check_visit[i] = false;
        }
    }
}


void DFS(int idx, int size)
{
    if (res.size() == size)
    {
        bool flag = true;
        for (int i = 0; i < res.size(); i++)
        {
            if (!m[i][res[i]])
            {
                flag = false;
                break;
            }
        }
        if (!flag)
        {
            return;
        }
        check_fl = true;
        check();

        if (check_fl)
        {
            string str = "";
            for (int i = 0; i < res.size(); i++)
            {
                str += res[i] + " ";
            }
            check_m[str] = true;
            answer++;
        }
        return;
    }


    for (int i = 0; i < list.size(); i++)
    {
        if (!visit[i])
        {
            visit[i] = true;
            res.push_back(list[i]);
            DFS(i, size);
            res.pop_back();
            visit[i] = false;
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int user_size = user_id.size();
    int ban_size = banned_id.size();

    for (int i = 0; i < ban_size; i++)
    {
        for (int j = 0; j < user_size; j++)
        {
            if (banned_id[i].size() == user_id[j].size())
            {
                bool flag = 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])
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                {
                    m[i][user_id[j]] = true;
                    if (!common[user_id[j]])
                    {
                        common[user_id[j]] = true;
                        list.push_back(user_id[j]);
                    }
                }
            }
        }
    }


    for (int i = 0; i < list.size(); i++)
    {
        visit[i] = true;
        res.push_back(list[i]);
        DFS(i, ban_size);
        res.pop_back();
        visit[i] = false;
    }


    return answer;
}