프로그래머스 문제 - 불량 사용자

프로그래머스 불량 사용자 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

이벤트에 응모한 아이디들을 입력받고 일부 문자를 '*'로 가린 제제 아이디 문자열을 입력받습니다.
제제 아이디 문자열과 같은 문자열은 당첨에서 제외되어야 하는 아이디로 분류됩니다.
'*'위치에는 어떤 단어든 들어갈 수 있습니다.
당첨에서 제외되어야 할 제제 아이디 목록은 몇가지 경우의 수가 가능한지 출력해야 합니다.

문제 풀이

일단 제제 아이디 문자열과 응모한 아이디들을 비교하여 당첨에서 제외되는 아이디인지 확인해줍니다.

각 문자열의 길이는 8이하이기 때문에 두 아이디의 각 자리를 비교하며 아이디들을 선별하였습니다.
문자열이 길이가 다르다면 애초에 제외되는 아이디가 아니기 때문에 넘어가줍니다.

//banned_id에 부합하는 아이디들 검색
for(int i = 0; i < banned_id.size(); i++)
{
    string curBanId = banned_id[i];
    for(string curId : user_id)
    {
        if(curId.size() == curBanId.size())
        {
            bool isBanned = true;
            for(int j = 0; j < curId.size(); j++)
            {
                if(curBanId[j] != '*')
                {
                    if(curId[j] != curBanId[j])
                    {
                        isBanned = false;
                    }
                }
            }
            if(isBanned)
            {
                check_id[i].push_back(curId);
            }
        }
    }
}

각각의 제제 아이디 문자열로 찾아낸 제외할 아이디들을 아이디 목록으로 만들어야 합니다.
아이디 목록은 기준을 맞추어서 만들어야 됩니다.

1. 목록에는 같은 아이디가 들어갈 수 없습니다.
2. 새로운 목록의 아이디들과 이미 등록된 목록들의 아이디들이 달라야합니다.
   

기준을 맞춰서 목록을 만든다면 위와 같이 주어졌을 때 목록이 만들어지게 됩니다.
저는 DFS를 통해 아이디 목록을 만들고 중첩을 없애기 위하여 set컨테이너를 사용하였습니다.

void dfs(int index, int idNum, vector<string> ban_id, vector<string> used_id)
{
    if(index == idNum)
    {
        //중첩 확인을 위해 sort진행
        sort(ban_id.begin(), ban_id.end());
        answer_id.insert(ban_id);
        return;
    }
    
    for(int i = 0; i < check_id[index].size(); i++)
    {
        bool isUsed = false;
        for(string temp : used_id)
        {
            if(check_id[index][i] == temp)
            {
                isUsed = true;
            }
        }
        if(!isUsed)
        {
            ban_id.push_back(check_id[index][i]);
            used_id.push_back(check_id[index][i]);
            dfs(index+1, idNum, ban_id, used_id);
            ban_id.erase(ban_id.end());
            used_id.erase(used_id.end());            
        }
    }
}

전체 코드

이번 문제는 DFS와 set같은 여러 컨테이너와 알고리즘을 가지고 해결한 난이도가 있는 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<string> check_id[8];
//중첩을 없애기 위해 set사용
set<vector<string>> answer_id;

void dfs(int index, int idNum, vector<string> ban_id, vector<string> used_id)
{
    if(index == idNum)
    {
        //중첩 확인을 위해 sort진행
        sort(ban_id.begin(), ban_id.end());
        answer_id.insert(ban_id);
        return;
    }
    
    for(int i = 0; i < check_id[index].size(); i++)
    {
        bool isUsed = false;
        for(string temp : used_id)
        {
            if(check_id[index][i] == temp)
            {
                isUsed = true;
            }
        }
        if(!isUsed)
        {
            ban_id.push_back(check_id[index][i]);
            used_id.push_back(check_id[index][i]);
            dfs(index+1, idNum, ban_id, used_id);
            ban_id.erase(ban_id.end());
            used_id.erase(used_id.end());            
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    
    //banned_id에 부합하는 아이디들 검색
    for(int i = 0; i < banned_id.size(); i++)
    {
        string curBanId = banned_id[i];
        for(string curId : user_id)
        {
            if(curId.size() == curBanId.size())
            {
                bool isBanned = true;
                for(int j = 0; j < curId.size(); j++)
                {
                    if(curBanId[j] != '*')
                    {
                        if(curId[j] != curBanId[j])
                        {
                            isBanned = false;
                        }
                    }
                }
                if(isBanned)
                {
                    check_id[i].push_back(curId);
                }
            }
        }
    }
    //부합하는 아이디들을 가지고 중첩되지 않는 아이디 목록을 만듬
    dfs(0, banned_id.size(), vector<string>(), vector<string>());
    //중첩되지 않는 아이디 목록의 수
    answer = answer_id.size();
    
    return answer;
}

출저

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