문제풀이
제재 아이디 목록(banned_id)의 각 아이디에 해당하는 모든 조합의 경우의 수를 구해야 하기 때문에 DFS를 활용해 가능한 모든 조합 구해보기로 했다.
그리고 구한 조합을 HashSet에 저장하여 중복값을 제거하고, HashSet의 사이즈를 반환하면 경우의 수를 구할 수 있다.
🤔 제재 아이디와 유저 아이디 비교 방법?
유저 아이디 문자열과 제재 아이디 문자열을 비교해서 동일한 패턴을 가지고 있는지 비교해야 하기 때문에 String.matches() 메서드를 이용했다.
contains() VS matches()
- contains() : 인자로 전달된 문자열의 존재 여부에 관한 결괏값 반환
- matches() : 정규표현식을 인자로 받고 동일한 패턴의 문자열인지에 관한 결괏값 반환
정규식에서는 '.' 이 어떤 문자 1개를 의미하기 때문에 제제 아이디에서 '*'로 표시된 부분을 '.'으로 replace 해주었다.
🤔 DFS 활용한 조합 구하기
이제 깊이우선탐색을 활용해 유저 ID에서 제재 ID에 해당하는 아이디를 탐색하고 제재 ID의 모든 조합을 구해보자.
유저 ID 목록을 탐색하면서 아직 탐색하지 않았고, 제재 ID와 패턴이 동일한 문자열을 조합이 될 result 문자열에 추가해준다. 이때 다른 제재 아이디와의 구분을 위해 공백을 두어 넣어주었다.
그리고 제재 ID에 해당하는 ID를 모두 찾았다면(index == banned_id.length) 조합을 HashSet에 넣어주었다.
이때 주의할 점이 있다. 문제의 제한사항을 보면
"제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다."
라는 항목이 있다. 즉 "A B" 나 "B A" 나 같다는 말이다.
따라서 공백으로 나눈 조합 문자열(result)을 공백을 기준으로 String[] 배열로 변환하여 Arrays.sort() 메서드를 이용해 사전순으로 한 번 정렬해준 뒤 , 다시 새 문자열에 추가하여 조합 값을 한 번 가공해주었다.
가공한 조합은 이제 HashSet에 들어갈 수 있다!
깊이우선탐색이 끝나면 제재 ID 패턴에 해당하는 아이디 조합의 모든 경우의 수가 HashSet 안에 들어가 있을 것이다. 그럼 HashSet의 size()만 반환해주면 된다.
소스코드
import java.util.Arrays;
import java.util.HashSet;
class Solution {
HashSet<String> banned_id_list;
boolean[] visited;
private void getBannedId_dfs(int index, String result, String[] user_id, String[] banned_id) {
if (index == banned_id.length) {
String[] arr = result.split(" ");
Arrays.sort(arr);
String res = "";
for(String id : arr) {
res += id;
}
banned_id_list.add(res);
return;
}
for(int i = 0; i < user_id.length; i++) {
if (!visited[i] && user_id[i].matches(banned_id[index])) {
visited[i] = true;
getBannedId_dfs(index + 1, result + " " + user_id[i], user_id, banned_id);
visited[i] = false;
}
}
}
public int solution(String[] user_id, String[] banned_id) {
banned_id_list = new HashSet<>();
// 정규식 활용 위한 제재 아이디 형식 변환
for(int i = 0; i < banned_id.length; i++) {
banned_id[i] = banned_id[i].replace('*', '.');
}
visited = new boolean[user_id.length];
getBannedId_dfs(0, "", user_id, banned_id);
return banned_id_list.size();
}
}후기
Level3 문제답게, 그리고 카카오 문제답게 DFS도 조건에 고려해야 할 사항들이 많이 있더라..
그리고 정규식을 이용해서 문자열 패턴 비교를 간단히 한다든가, HashSet을 이용해 경우의 수의 중복을 제거한다든가 문제 푸는 센스가 필요한 듯 하다.
Level 3 문제는 역시 쉽지 않다..!
