불량 사용자
문제
https://school.programmers.co.kr/learn/courses/30/lessons/64064
풀이
우선 banned_id 마다 매핑되는 user_id를 구해야 한다고 생각했다.
그러면 banned_id와 user_id가 '*' 빼고 모두 일치해야 해당 user_id가 ban 당한 아이디일 확률이 높다.
banned_id와 user_id 매핑
하나의 banned_id와 매핑되는 user_id들을 모두 구해야 한다.
user_id = ["frodo", "fradi", "crodo", "abc123", "frodoc"]
banned_id = ["fr*d*", "abc1**"]banned_id 중 하나가 ban, user_id 중 하나가 user 라고 해보자.
- ban의 길이와 user의 길이가 일치
- 서로의 문자를 하나씩 비교
2-1. 만약 서로 다른 문자가 나왔는데- ban의 문자가 '*'라면 ban당한 user일 확률이 높다. (isBan = true)
- 만약 '*'가 아니고 완전 다른 문자라면 바로 탈락 (isBan = false)
- 문자열에 대한 비교가 끝났는데 isBan = true라면 list에 넣는다.
3-1.List<List<String>> list = new ArrayList<>();
를 사용하여 하나의 ban 마다 매핑되는 user를 넣는다.
list = [
["frodo","fradi"] ("fr*d*"와 매핑) ,
["abc123"] ("abc1**"와 매핑)
]
이 된다는 것이다.
조합 (Combination)
이렇게 하나의 banned_id에 매핑되는 user_id들을 구했으면,
조합(combination)으로 경우의 수를 구해야한다.
근데 Java에서는 combination을 구하는 라이브러리가 따로 없어서 ..
찾아보니까 재귀로 해결할 수 있었다.
- banned_id에 매핑된 user_id를 하나씩 꺼내면서 중복 확인을 하고 Set에다가 넣는다.
- 만약 Set의 크기가 banned_id의 개수와 동일하게 되면 재귀에서 빠져나오고,
- Set에 들어간 순으로 다시 삭제하는 과정을 진행한다.
예를 들어,
list = [
["frodo","fradi"] ("fr*d*"와 매핑) ,
["abc123"] ("abc1**"와 매핑)
]
Set<Set<String>> combinations = new HashSet<>(); //조합들을 모아놓는 곳
Set<String> current = new HashSet<>();1) 첫번째 "fr*d*"와 매핑된 아이디 중 "frodo"를 꺼내 current에 넣는다.
current = [ "frodo" ]2) 재귀를 통해 다음 banned_id인 "abc1**"와 매핑된 아이디 "abc123"을 꺼내 current에 넣는다.
current = [ "frodo", "abc123" ]3) 현재 banned_id의 크기인 2와 current의 크기와 같으므로 해당 Set을 하나의 조합으로 인식하여 combinations에 넣는다.
combinations = [ ["frodo", "abc123"] ]4) 이후 재귀에서 반환되어, "abc123"을 current에서 지우고 "abc1**"와 매핑되는 아이디가 더 없기 때문에 끝이 난다. (재귀에서 탈출)
current = [ "frodo" ]5) 다음은 "frodo"를 current에서 지우고 "fr*d*"와 매핑되는 다음 아이디로 넘어가, "fradi" 를 current에 넣는다.
current = ["fradi"]6) 재귀를 통해 다음 banned_id인 "abc1**"와 매핑된 아이디 "abc123"을 꺼내 current에 넣는다.
current = [ "fradi", "abc123" ]7) 이 또한 현재 banned_id의 크기인 2와 current의 크기와 같으므로 해당 Set을 하나의 조합으로 인식하여 combinations에 넣는다.
combinations = [ ["frodo", "abc123"]. ["fradi", "abc123"] ]8) 재귀에서 반환되어, 위에 방식과 같이 매핑되는 다음 아이디가 있으면 진행, 없으면 재귀에서 탈출한다.
9) 현재는 "fr*d*"와 "abc1**"이 매핑되는 아이디 모두 반복문을 돌았으니 완전히 재귀에서 탈출한다.
그리고 마지막 combinations의 크기를 반환해주면, 제외되어야 할 아이디 목록의 경우의 수를 구할 수 있다.
코드
public class BadUser {
public int solution(String[] user_id, String[] banned_id) {
List<List<String>> list = new ArrayList<>();
for (int i=0; i<banned_id.length; i++){
list.add(new ArrayList<>());
}
//하나의 ban 닉네임에 연관된 user 닉네임을 나열
int index = 0;
for (String ban : banned_id){
for (String user : user_id){
boolean isBan = false;
if (ban.length() == user.length()){ //일단 길이가 같아야 비교 시작
for (int i=0; i<ban.length(); i++){
if (ban.charAt(i) != user.charAt(i)){ //만약 다른 문자가 나왔을 때
if (ban.charAt(i) == '*'){ //별이면 통과 (ban당한 닉네임일 확률이 큼)
isBan = true;
} else {
isBan = false; //그냥 다른 문자이면 탈락
break;
}
}
}
if (isBan) {
//만약 ban 닉네임과 일치한다면
list.get(index).add(user); //추가
}
}
}
index++; //다음 ban 닉네임으로 이동
}
Set<Set<String>> combinations = new HashSet<>();
//조합을 만들기 위한 Set<Set>
getAllCombinations(list, 0, new HashSet<>(), combinations);
//재귀를 통해서 만든다.
return combinations.size(); //마지막으로 반환되는 조합의 개수
}
private static void getAllCombinations(List<List<String>> banned_id, int index, Set<String> current, Set<Set<String>> uniqueCombinations) {
if (index == banned_id.size()) { //ban 닉네임의 개수와 동일하면 return
uniqueCombinations.add(new HashSet<>(current)); //current가 현재 만들어진 조합으로 추가한다.
return;
}
for (String user : banned_id.get(index)) { //banned_id에 맞는 user_id를 하나씩 꺼내고
if (!current.contains(user)) { //current 에다가 없으면 넣는다.
current.add(user);
getAllCombinations(banned_id, index + 1, current, uniqueCombinations); //다음 banned_id로 넘어간다.
current.remove(user); //여기는 current가 조합이 만들어져서 추가한 후 이므로 다시 삭제하는 과정
}
}
}