문제 설명
개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.
예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면
| 응모자 아이디 |
|---|
| frodo |
| fradi |
| crodo |
| abc123 |
| frodoc |
다음과 같이 불량 사용자 아이디 목록이 전달된 경우,
| 불량 사용자 |
|---|
| fr*d* |
| abc1** |
불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.
| 제재 아이디 |
|---|
| frodo |
| abc123 |
| 제재 아이디 |
|---|
| fradi |
| abc123 |
이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.
[제한사항]
- user_id 배열의 크기는 1 이상 8 이하입니다.
- user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
- 응모한 사용자 아이디들은 서로 중복되지 않습니다.
- 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
- banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
- banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
- 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다.
- 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.
- 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
- 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.
[입출력 예]
| user_id | banned_id | result |
|---|---|---|
| ["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["fr*d*", "abc1**"] | 2 |
| ["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["*rodo", "*rodo", "******"] | 2 |
| ["frodo", "fradi", "crodo", "abc123", "frodoc"] | ["fr*d*", "*rodo", "******", "******"] | 3 |
입출력 예에 대한 설명
입출력 예 #1
문제 설명과 같습니다.
입출력 예 #2
다음과 같이 두 가지 경우가 있습니다.
| 제재 아이디 |
|---|
| frodo |
| crodo |
| abc123 |
| 제재 아이디 |
|---|
| frodo |
| crodo |
| frodoc |
입출력 예 #3
다음과 같이 세 가지 경우가 있습니다.
| 제재 아이디 |
|---|
| frodo |
| crodo |
| abc123 |
| frodoc |
| 제재 아이디 |
|---|
| fradi |
| crodo |
| abc123 |
| frodoc |
| 제재 아이디 |
|---|
| fradi |
| frodo |
| abc123 |
| frodoc |
문제 풀이 방법
처음에는 간단하게 풀리는 문제라고 생각했지만 문제의 조건들을 모두 고려하여 해결 하면 조금 더 많은 고민이 필요 했다.
우선 풀이 단계는 크게 2개로 나눌 수 있다.
- banned_id 를 정규식으로 변환 후 match 를 이용해서 아이디를 찾는다.
- DFS 방법을 이용하여 아이디가 중복 되지 않게 아이디의 짝을 찾는다. 이때 HashSet<HashSet> 을 통해서 구한다.
정규식 관련 내용은 여기를 참고하면 좋을 것 같다.
정규식에서 '.' 은 임의의 문자를 의미하며, ***** 을 모두 **.**으로 변경하였다.
코드로 표현하면 String pattern = bannedId.replace('*', '.'); 이렇게 된다.
Pattern.matches(정규식, 비교대상 문자열) 를 통해서 정규식과 일치 여부를 알 수 있다.
public static void dfs(HashSet<String> add, int depth) {
if (depth == bannedUserList.size()) {
result.add(new HashSet<>(add));
return;
}
// depth번째에 들어갈 수 있는 아이디 목록에서 뽑음
for (String userId : bannedUserList.get(depth)) {
if (!add.contains(userId)) {
add.add(userId);
dfs(add, depth + 1);
add.remove(userId);
}
}
}이 부분이 제제 아이디의 리스트를 구하는 메소드이다.
일반적인 DFS 코드와 동일하게 생각하면 되며, DFS 에서 boolean[] visited 형태를 주로 사용했다면 remove 는 visited 배열에서 true 를 다시 false 로 변경하는 것과 동일하게 생각하면 된다.
최종 결과 Result hashset 에는 위와 같은 값이 들어 가게 된다.
즉, result 크기가 결과가 된다.
전체 코드
import java.util.*;
import java.util.regex.Pattern;
class Solution {
public static HashSet<HashSet<String>> result;
public static ArrayList<ArrayList<String>> bannedUserList;
public int solution(String[] user_id, String[] banned_id) {
result = new HashSet<HashSet<String>>();
bannedUserList = new ArrayList<ArrayList<String>>();
for (String bannedId : banned_id) {
bannedUserList.add(getMatchesId(bannedId, user_id));
}
dfs(new HashSet<String>(), 0);
return result.size();
}
public static ArrayList<String> getMatchesId(String bannedId, String[] user_id) {
// 불량 사용자 아이디 정규 표현식으로 변환
// 정규 표현식에서 '.' = 임의의 문자열 1개
String pattern = bannedId.replace('*', '.');
ArrayList<String> valueList = new ArrayList<>();
for (String userId : user_id) {
// 정규 표현식 턴에 맞는 유저 아이디 담음
if (Pattern.matches(pattern, userId))
valueList.add(userId);
}
return valueList;
}
public static void dfs(HashSet<String> add, int depth) {
if (depth == bannedUserList.size()) {
result.add(new HashSet<>(add));
return;
}
// depth번째에 들어갈 수 있는 아이디 목록에서 뽑음
for (String userId : bannedUserList.get(depth)) {
if (!add.contains(userId)) {
add.add(userId);
dfs(add, depth + 1);
add.remove(userId);
}
}
}
}