불량사용자 문제 바로가기
이번 문제는 살짝 난이도가 있는 문제였다.
구글링을 해보니 DFS로 푸신 분들이 계신거 같은데,,, 아무리 코드를 읽어봐도 사실 이해가 잘 되지 않았다.
나는 순열을 통해서 문제를 풀었는데, 퍼뮤테이션을 이용해서 문제를 설명해 보도록 하겠다.
문제의 핵심은 2가지이다.
- BackTracking이 불가능?하므로 모든 경우의 수를 판단할것,
- 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.
이 조건을 만족시키기 위해 set자료구조를 사용할것
자, 그냥 일단 먼저 문제를 풀기 위해서 어떤 로직을 따라야할지 설명해 보도로 하겠다.
예시 2번으로 설명을 해보자면,
["frodo", "fradi", "crodo", "abc123", "frodoc"]
["rodo", "rodo", "**"]
2
자 먼저 userId에서 나올 수 있는 모든 조합을 따진다.
frodo,fradi,crodo,abc123,frodoc
frodo,fradi,crodo,frodoc,abc123
,,,
fradi,frodo,crodo,abc123,frodoc
,,,
등등등 쭉 나열이 될것이다.
이것을 bannedId와 비교를 하는것이다.
조합중에서 첫번째를 가져와 설명을 하면
frodo는 rodo와 같다.
고로 myfind에 넣는다. myfind[frodo]
그리고 rodo를 지운다.
그다음 fradi이다. fradi는 rodo와 *x6개와 다르다. pass
그다음 crodo는 rodo가 맞다 myfind에 넣고 rodo를 지운다.
myfind[frodo,crodo]
그다음 별 6개짜리를 frodo,crodo,abc123넣는다.
그다음 이제 bannedId가 없을것이다.
그다음은 조합은 frodoc가 먼저온다. 그러면
myfin에[frodo,crodo,frodoc]이 될것이다.
이런식으로 1번핵심을 처리한다.
근데 문제가 뭐냐면
frodo,fradi,crodo,abc123,frodoc
frodo,crodo,fradi,abc123,frodoc
이런식의 조합을 살펴보자
frodo와 crodo,abc123이 myfind에 들어가고 동일한 조합이 되는것이다.
그래서 myfind에서 각 문자를 꺼내와 temp에 넣고
이 temp를 set에 넣는다.
set에는 중복이 되지않는다.
이것이 두번째 핵심이다.
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
bool correct(string bid, string uid){
for(int i=0;i<bid.size();i++){
if(bid[i]=='*'){
continue;
}else if(bid[i]!=uid[i]){
return false;
}
}
return true;
}
int solution(vector<string> user_id, vector<string> banned_id) {
vector <int> v;
for(int i=0;i<user_id.size();i++){
v.push_back(i);
}
set<string> s;
//첫번째 핵심을 위해 do while next_permutation이용
do{
vector<string> target;
vector<string> myfind;
for(int i=0;i<banned_id.size();i++){
target.push_back(banned_id[i]);
}
for(int i=0;i<v.size();i++){
string uid=user_id[v[i]];
for(int j=0;j<target.size();j++){
//문자열이 동일한지 비교하는 로직
string temp = target[j];
if(temp.size()==uid.size() && correct(temp,uid)){
target.erase(target.begin()+j);
myfind.push_back(uid);
break;
}
}
}
//두번째 핵심 처리 로직
if(myfind.size()==banned_id.size()){
sort(myfind.begin(),myfind.end());
string tmp="";
for(int i=0;i<myfind.size();i++){
tmp+=myfind[i];
}
s.insert(tmp);
}
}while(next_permutation(v.begin(),v.end()));
return s.size();
}근데 아마 내가 소마 1차 4번째 문제에서 떨어진것과 같이...
흑..
이게 과연 시간복잡도 내에 해결이 가능한가? 이게 중요한것이다.
- do while nexpermutation은 v의 size가 n이라고 가정하면 O(n!)이다.
- 내부에 이중포문이 있는데, v.size와 targetsize를 동일하게 n으로 잡으면 n^2이다. 고로 O(n!*n^2)이다.
- 그 밑에있는 for문은 무시해도 좋다. 왜냐하면 n!보다 현저히 빠르기 때문이다.
종합해보면 id가 최대 8개라 하였으므로 O(8! * 64)이다.
O(2,580,480)
이를 통해 계산해보면 2,580,480번 최대 계산하므로 1억이 1초임을 감안하면
매우 빠른 속도로 계산이 가능하다.
고로, 순열을 계산할때는 최대 계산을 확인 해봐야겠다...
