우리가 사용자를 밴 할껀데 사실 나도 누가 밴 해야하는지 원본을 잃어버렸어... 혹시 가능한 경우의 수... 니가 좀 구해줄래? 일단 한번 보고 다 밴하던가 할게....
문자열에 별표가 들어있다. 이 문자열의 별표는 알파벳과 숫자로 대체 가능하다. 조건에 맞는 유저들을 찾아라.
자세한 문제 설명과 제한 사항은 프로그래머스 홈페이지 참고. 문제풀러가기
별표는 무조건 단 하나의 문자와 대응 가능하기 때문에 문제는 어렵지 않다.
2차원 배열을 만든 후 banned_id에 대응하는 user_id를 체크하고 각 경우의 수를 구한다면 나름 쉽게 풀 수 있다.
프로그래머스 사이트가 아닌, visual studio 에서 코드를 작성해서 그대로 가져온 것 입니다. 일부 테스트 코드가 존재합니다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool isMatch[10][10]; // ban, user 순
bool isUsed[10];
int bansize = 0;
vector<vector<int>> ansVec;
bool check(string userid, string banid);
void travel(int banidx, int userNum, vector<int> ans);
int solution(vector<string> user_id, vector<string> banned_id);
int main() {
string s = "frodo";
string test = s.substr(4);
vector<string> user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
vector<string> banned_id = { "fr*d*", "abc1**" };
solution(user_id, banned_id);
}
int solution(vector<string> user_id, vector<string> banned_id) {
int answer = 1;
bansize = banned_id.size();
for (size_t i = 0; i < banned_id.size(); i++)
for (size_t j = 0; j < user_id.size(); j++)
if (check(user_id[j], banned_id[i]))
isMatch[i][j] = true;
int startLine = -1;
vector<int> ans;
travel(0, user_id.size(), ans);
return ansVec.size();
}
void travel(int banidx, int userNum ,vector<int> ans) {
if (banidx == bansize) {
sort(ans.begin(), ans.end());
for (int i = 0; i < ansVec.size(); i++) {
bool flag = true;
for (int j = 0; j < ansVec[i].size(); j++){
if (ans[j] != ansVec[i][j]) flag = false;
}
if (flag == true) return;
}
ansVec.push_back(ans);
return;
}
bool isExist = false;
for (size_t i = 0; i < userNum; i++)
if (isMatch[banidx][i] == true) isExist = true;
if (isExist == false) {
travel(banidx + 1, userNum, ans);
return;
}
for (size_t i = 0; i < userNum; i++){
if (isUsed[i] == true) continue;
if (isMatch[banidx][i] == true) {
ans.push_back(i);
isUsed[i] = true;
travel(banidx + 1 , userNum, ans);
ans.pop_back();
isUsed[i] = false;
}
}
}
bool check(string user, string ban) {
if (user.size() != ban.size()) return false;
for (size_t i = 0; i < ban.size();i++)
{
if (user[i] != ban[i] && ban[i] != '*') return false;
}
return true;
}
BANNED 당한 유저를 * 로 처리 해주는 센스...
항상 생각 하지만 문제는 현실의 요구를 반영하지 않는 것 같다.