알고리즘/프로그래머스
프로그래머스 불량 사용자
pureworld
2021. 5. 14. 11:31
C++로 풀었습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
vector<string> ban;
vector<string> user;
//user 사용했는지 체크하는 배열
bool visited[20];
vector<string> ret;
vector<int> match[20];
//문자 매치 가능한지 확인하는 함수
bool isMatch(string a,string b){
if(a.length()!= b.length())
return false;
for(int i=0;i<a.length();i++){
if(a[i]!=b[i]){
if( !(a[i]=='*' ||b[i]=='*') )
return false;
}
}
return true;
}
void DFS( int pos ,vector<int> arr){
if(arr.size()==ban.size()){
sort(arr.begin(),arr.end());
string s;
for(int i=0;i<arr.size();i++){
s+=arr[i];
}
ret.push_back(s);
return;
}
if(pos>=ban.size())
return;
for(int i=0;i<match[pos].size();i++){
int str=match[pos][i];
if(!visited[str]){
visited[str]=1;
arr.push_back(str);
DFS(pos+1,arr);
visited[str]=0;
arr.pop_back();
}
}
}
int solution(vector<string> user_id, vector<string> banned_id) {
//전역변수 초기화
user=user_id; ban=banned_id;
for(int i=0;i<ban.size();i++){
for(int j=0;j<user.size();j++){
if(isMatch(ban[i],user[j]))
match[i].push_back(j);
}
}
memset(visited,0,sizeof(visited));
vector<int> v;
DFS(0,v);
int answer = 0;
sort(ret.begin(),ret.end());
ret.erase(unique(ret.begin(),ret.end()),ret.end());
answer=ret.size();
return answer;
}
|
cs |
문제를 풀기위해 생각한 포인트는 다음과 같습니다.
1. 밴유저가 선택가능한 유저를 구한다.
2. 밴유저가 선택가능한 모든 조합을 구함.
3. 중복 제거
코드로 구현은 다음과 같이했습니다.
1.banned_id와 user_id 비교해서 banned_id가 선택가능한 유저 후보 얻어서 match에 문자열대신 int형 배열로 저장.
2.DFS함수를 호출해 visited배열에 선택한 user를 기록하고 선택한 조합을 arr배열에 기록합니다.
3.밴유저수와 arr배열의 크기가 같아지면 조합을 완료한 것이고 중복 제거를 위해 정렬한뒤 간단하게 string s를 이용해
간단하게 vector<string> ret에 기록합니다.
4. DFS함수 종료후 밴유저가 선택가능한 모든 조합은 ret에 기록이 됩니다. erase,unique함수를 이용해 중복을 제거한 뒤
ret의 크기를 반환하면 정답입니다.