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

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

프로그래머스

 이 문제는 응모자 아이디 목록과 불량 사용자의 아이디 목록이 주어졌을 때, 제재 아이디 목록의 경우의 수를 리턴하는 문제이다. 처음에는 단순히 각각의 응모자 아이디와 각각의 불량 사용자 아이디를 하나하나 다 비교한 후, 가능한 수를 세면 될 것이라 생각했다. 하지만 이런 식으로 무지성으로 검사하다보면 중복되는 경우가 생긴다. (예를 들어, 가능한 불량 이용자 리스트가 ["aaa", "bbb"]와 ["bbb", "aaa"]는 서로 같은 경우이므로 하나로 봐야 한다.) 그렇기 때문에 불량 이용자가 될 수 있는 아이디를 저장하는 배열을 정렬한 후, 이미 본 적이 있는지를 검사하였다. 이를 위해 구상한 절차는 다음과 같다.

1. 가능한 모든 경우를 체크한다.
2. 모든 유저를 순서대로 검사한다.
   1. 만약 현재 유저가 매치되지 않았으면서 밴 리스트에 추가한다.
3. 만약 밴 리스트가 꽉 찼다면 (주어진 불량 아이디 수와 같다면) 가능한 경우인지 체크한다. 따로 정렬한 후, 체크할 것이기 때문에 별도로 만들어준다.
   1. 정렬 후, 만약 현재의 경우가 한 번도 본 적 없는 경우라면 모든 가능한 밴 리스트를 저장하는 배열에 저장한다.
4. 모든 경우를 저장한 배열의 길이를 반환한다.

 

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

#define MAX 10

vector<string> userIds;     // 주어진 응모자 목록
vector<string> bannedIds;   // 주어진 불량 사용자 목록
vector<int> bannedList;     // 
vector<vector<int>> allBannedLists;
bool isMatched[MAX];

// 아이디가 서로 매치되는지를 검사하는 함수
bool CanMatch(int userIdx, int banIdx)
{
	string userId = userIds[userIdx];
	string bannedId = bannedIds[banIdx];
    
    // 만약 단어의 길이가 애초에 다르다면 false를 반환
	if (userId.size() != bannedId.size())
		return false;
    
    // 서로 매치되면 true를, 안되면 false를 반환
	for (int i = 0; i < userId.size(); ++i)
	{
		if (bannedId[i] == '*')
			continue;
		if (userId[i] != bannedId[i])
			return false;
	}

	return true;
}

// 현재 밴 리스트가 이미 본 적 있는 경우인지를 검사하는 함수
bool Banned(vector<int> curBannedList)
{
	for (int i = 0; i < allBannedLists.size(); ++i)
	{   
        // 검사 후, 리스트가 서로 다르다면 isEqual = false가 될 것이다.
		bool isEqual = true;
		
        // 모두 정렬되어 있기 때문에 순서대로 검사한다.
		for (int k = 0; k < curBannedList.size(); ++k)
		{
			if (curBannedList[k] != allBannedLists[i][k])
			{
				isEqual = false;
				break;
			}
		}

		if (isEqual)
			return true;
	}

	return false;
}

// 당첨자와 불량 아이디를 서로 매치하는 함수
void Match(int banIdx)
{   
    // 3. 만약 밴 리스트가 꽉 찼다면 (주어진 불량 아이디 수와 같다면)
    // 가능한 경우인지 체크한다.
	if (banIdx >= bannedIds.size())
	{   
        // 따로 정렬한 후, 체크할 것이기 때문에 
        // 별도로 만들어준다.
		vector<int> curBannedList = bannedList;
		sort(curBannedList.begin(), curBannedList.end());
        
        // 3-1. 정렬 후, 만약 현재의 경우가 한 번도 본 적 없는 경우라면
        // 모든 가능한 밴 리스트를 저장하는 배열에 저장한다.
		if (Banned(curBannedList) == false)
			allBannedLists.push_back(curBannedList);
	
		return;
	}
    
    // 2. 모든 유저를 순서대로 검사한다.
	for (int userIdx = 0; userIdx < userIds.size(); ++userIdx)
	{
        // 2-1. 만약 현재 유저가 매치되지 않았으면서
		if (isMatched[userIdx] == false)
		{   
            // 현재 불량 사용자와 매치가 가능하다면
			if (CanMatch(userIdx, banIdx))
			{
                // 밴 리스트에 추가한다.
                
				isMatched[userIdx] = true;
				bannedList.push_back(userIdx);

				Match(banIdx + 1);
				
				bannedList.pop_back();
				isMatched[userIdx] = false;
			}
		}
	}
}

int solution(vector<string> user_id, vector<string> banned_id)
{	
	userIds = user_id;
	bannedIds = banned_id;
    
    // 1. 가능한 모든 경우를 체크한다.
	Match(0);
	
    // 4. 모든 경우를 저장한 배열의 길이를 반환한다.
	return allBannedLists.size();
}