⚙️ 알고리즘 분류 : DFS
🔠 언어 : c++
🤫 힌트.
완전탐색인듯 완전탐색 아닌 완전탐색 같은...(사실 힌트 줘도 못 풀 듯)
✏️ 풀이.
문제 풀이 단계
1) banned_id와 user_id를 비교하며, 각 banned_id에 부합하는 user_id를 저장한다.
2) dfs를 이용한다. dfs의 인자는 banned_id의 index다. index 0부터 시작하여 1)에서 구한 해당 banned_id의 user_id를 하나씩 체크해간다.
➡️ 이 부분 고민이 많았다. 인자에 string을 하나 만들어서 user_id를 하나씩 붙여나갈까 싶었다. 근데 이렇게 되면 ABC랑 ACB랑 다른 것으로 구분할 것 같아서 어떻게 해야하나 싶었다. 과거의 나는 배열을 하나 만들어서 그냥 user_id의 index를 체크했다.
3) 만약 모든 banned_id를 봤다면 여태껏 봤다고 체크한 user_id를 하나의 string으로 붙인다. 그리고 중복제거가 되는 자료구조에 넣는다
➡️ 이번엔 map으로 했지만, 예전에 푼 코드를 보면 set에 넣었다. 문제에서 중복되는 여러 경우는 하나로 보라고 해서 이를 반영했다.
⚠️ 헤맨 부분.
애초에 dfs라고 생각을 안 했다... 그리고 dfs로 풀어야 하는 걸 알았을 때도 어떻게 풀어야 할지 감이 안 왔다.
처음엔 예제3에서 자꾸 걸렸다. 도대체 어떻게 답이 3이 나오나...!
그 부분에서 꽤나 고민을 했다. 어떻게 구현을 해야할지.
그리고 dfs로 풀어야 하는 걸 알았을 때, '문자열의 각 문자를 하나씩 붙이는 방법인가?' 하고 생각했다. 접근이 잘못 됐었다.
하지만 꽤 곰곰히 생각했었기에, 답을 보고 '이건 맞았네' 싶은 부분도 있었다.
1. 중복되지 않은 조합의 개수를 찾아내야 했기에 문자열에 다 붙여서 구분해야 하지 않을까 하고 생각했다.
순위 검색 문제를 참고해서 생각했다.
2. banned_id와 user_id를 하나씩 비교해보며 적합한 애들 찾는 것도 맞았다. 그 뒤에 처리가 dfs였나 아니였냐의 문제였다.
그래도 나름 시간을 들여서 생각한 부분이 정답에 근접했다.
dfs로 이렇게 풀 수 있다고는 생각을 잘 못했다. 아예 생각조차 못한 것이 헤맨 부분이라고 생각한다.
👩🏻💻 코드.
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<int> v[10];
int ch[10];
vector<string> banned, user;
map<string,int> m;
void dfs(int idx){
if(idx==banned.size()){
string tmp="";
// 여태껏 본 user_id를 하나의 string으로 만든다.
for(int i=0; i<user.size(); i++){
if(ch[i]) tmp+=user[i];
}
m[tmp]++;
return;
}
// banned_id[idx]에 부합하는 user_id를 하나씩 본다.
for(int i=0; i<v[idx].size(); i++){
if(ch[v[idx][i]]) continue;
ch[v[idx][i]]=1;
dfs(idx+1);
ch[v[idx][i]]=0;
}
}
int solution(vector<string> user_id, vector<string> banned_id) {
banned=banned_id, user=user_id;
// 각 banned_id에 부합한 user_id 저장
for(int i=0; i<banned_id.size(); i++){
for(int j=0; j<user_id.size(); j++){
if(banned_id[i].size()!=user_id[j].size()) continue;
bool isRight=true;
for(int k=0; k<user_id[j].size(); k++){
if(banned_id[i][k]!=user_id[j][k]&&banned_id[i][k]!='*'){
isRight=false;
break;
}
}
if(isRight) v[i].push_back(j);
}
}
dfs(0);
return m.size();
}아래는 예전에 푼 코드. 얘가 더 깔끔해보인다!
#include <string>
#include <vector>
#include <set>
using namespace std;
vector<string> user, banned;
int ch[9];
set<string> s;
// 각 banned_id에 부합한 user_id 저장
bool is_possible(int ban_idx, int user_idx){
if(banned[ban_idx].length()!=user[user_idx].length()) return false;
if(ch[user_idx]) return false;
for(int i=0; i<banned[ban_idx].length(); i++){
if(banned[ban_idx][i]=='*') continue;
if(banned[ban_idx][i]!=user[user_idx][i]) return false;
}
return true;
}
void dfs(int ban_idx){
if(ban_idx==banned.size()) {
string sum="";
for(int i=0; i<user.size(); i++){
if(ch[i]) sum+=user[i];
}
s.insert(sum);
return;
}
for(int i=0; i<user.size(); i++){
if(is_possible(ban_idx, i)){
ch[i]=1;
dfs(ban_idx+1);
ch[i]=0;
}
}
}
int solution(vector<string> user_id, vector<string> banned_id) {
int answer = 0;
user = user_id, banned=banned_id;
dfs(0);
return answer=s.size();
}😎 후기.
사실 이 문제는 이전에 2번 정도 푼 문제다.
그때 풀었을 때도 지금처럼 기록을 해둬서 다시 봤는데, 이번 포함 3번 모두 접근 방법이 똑같았다ㅎㅎ... 변화가 없네. 변화 쿠다사이...!
dfs 문제를 생각하면 으레 2차원 배열 관련 문제를 생각한다.
dfs를 이용해서 이렇게 문제를 풀 수 있음을 깨닫는다.
오마카세 급은 아니라서 준오마카세!!!
시간이 지난 후에 다시 풀 땐, dfs 생각을 할 수 있길...!
