프로그래머스 - 불량 사용자 (C++)

Pixabay로부터 입수된 succo님의 이미지 입니다.

---

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

프로그래머스

 

 이 문제는 응모자 아이디와 불량 사용자 아이디가 주어졌을 때, 불량 사용자 아이디가 가능한 응모자 아이디들을 구하는 문제이다. 불량 사용자 아이디 하나당 응모자 아이디 하나를 매치해야 하기에 일종의 순열 문제라고 할 수 있다. 그렇기에 순열을 이용하여 응모자 아이디와 불량 사용자 아이디를 매치하면서 모든 불량 사용자 아이디가 매치된다면 답을 1 증가시켜주면서 답을 구할 수 있을 것이다. 

 하지만 모두 매치되었다고 해서 답을 1 증가시키면 안된다. 왜냐하면 중복되는 경우가 있기 때문이다. 예를 들어 2번 예제의 경우, ["*rodo", "*rodo", "******"]는 매치 순서에 따라 [frodo, crodo, frodoc]도 될 수 있고 [crodo, frodo, frodoc]도 될 수 있다. 그렇기에 중복이 되지 않게 검사하는 과정을 추가해주어야 한다. 본인은 매치하면서 얻은 모든 결과를 저장해둔 후, 중복되는 것이 있는지 하나 하나 검사하여 답을 판단하였다. 아래는 답을 구하는 과정이다.

1. 순열을 계산하는 방식을 이용해 매치되는 경우를 판단한다. 이 때, 함수의 인자는 불량 사용자 아이디의 인덱스(bannedIdx)이다.
2. 응모자 아이디를 처음부터 끝까지, 현재 불량 사용자 아이디와 매치되는지를 검사한다. 만약 매치된다면 매치된 아이디를 저장하는 벡터(matchingList)에 이를 push한다.
3. 만약 모든 불량 사용자 아이디가 매치되었다면, 현재 리스트가 중복되는지 아닌지를 모든 매치된 리스트(allMatchingList)와 검사한다. 이 때, 비교의 편의를 위해서 미리 정렬을 한 후 비교를 한다.
4. 만약 현재 리스트가 중복되지 않는다면 모든 매치된 리스트(allMatchingList)에 push한 후, 답을 1 증가시킨다.

 

#include <string>
#include <vector>
#include <algorithm>
#define MAX 10
using namespace std;

int answer;
bool matched[MAX];
vector<string> userIds;
vector<string> bannedIds;
vector<string> matchingList;
vector<vector<string>> allMatchingList; 

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

bool UniqueMatchingList()
{
    bool isUnique = true;
    
    vector<string> curMatchingList = matchingList;
    sort(curMatchingList.begin(), curMatchingList.end());
    
    for (int i = 0; i < allMatchingList.size(); ++i)
    {
        bool isSame = true;
        
        for (int k = 0; k < allMatchingList[i].size(); ++k)
        {
            if (allMatchingList[i][k] != curMatchingList[k])
            {
                isSame = false;
                break;
            }
        }
        
        if (isSame)
            return false;
    }
    
    allMatchingList.push_back(curMatchingList);
    
    return true;
}

void Check(int bannedIdx)
{
    if (bannedIdx >= bannedIds.size())
    {
        if (UniqueMatchingList() == true)
            ++answer;
        
        return;
    }
    
    for (int i = 0; i < userIds.size(); ++i)
    {
        if (matched[i] == false)
        {
            string userId = userIds[i];
            
            if (Match(userId, bannedIds[bannedIdx]) == true)
            {
                matched[i] = true;
                matchingList.push_back(userId);
                
                Check(bannedIdx + 1);
                
                matchingList.pop_back();
                matched[i] = false;
            }
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    
    userIds = user_id;
    bannedIds = banned_id;
    
    Check(0);
    
    return answer;
}