2019 카카오 불량 사용자 자바

문제는 다음과 같다.
https://school.programmers.co.kr/learn/courses/30/lessons/64064

풀이는 다음과 같다.

import java.util.*;

class Solution {
    static String[] check;
    static boolean[] visited;
    static HashSet<HashSet<String>> answer = new HashSet<>();
    
    public int solution(String[] user_id, String[] banned_id) {
        check = new String[banned_id.length];
        visited = new boolean[user_id.length];
        
        backTracking(0, user_id, banned_id);
        
        return answer.size();
    }
    
    static void backTracking(int depth, String[] user, String[] ban) {
        if(depth == ban.length) {
            
            boolean allOk = true;
            
            for(int i = 0 ; i < ban.length ; i++) {
                
                if(!isOk(check[i], ban[i])) {
                    allOk = false;
                    break;
                }
            }
            
            
            if(allOk) {
                HashSet<String> s = new HashSet<>();
                for(int i = 0 ; i < check.length ; i++) {
                    s.add(check[i]);
                }
                answer.add(new HashSet<>(s));
            }

            return;
        }
        
        
        for(int i = 0 ; i < user.length ; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            check[depth] = user[i];
            backTracking(depth+1, user, ban);
            visited[i] = false;
        }
    }
    
   
    
    static boolean isOk(String s1, String s2) {
        if(s2.length() != s1.length()) return false;
        
        for(int i = 0 ; i< s1.length() ; i++) {
            if(s2.charAt(i) == '*') continue;
            
            if(s1.charAt(i) != s2.charAt(i)) return false;
        }
        
        return true;
    }
}

---

isOk 함수는, 두개의 String을 기준으로
체크해줄 아이디와, 불량 사용자 아이디가 매치되는지 확인한 후
boolean을 리턴해준다.

예를 들어, fr*d*와 frodo를 확인하면 true를 return해준다.

길이를 비교한 후,
길이가 같다면 charAt()으로
순서대로 글자를 확인해준 후 
boolean을 return해준다.

---

backTracking 함수는, 전체 아이디중에서 무작위로 뽑으며
확인할 개수만큼 뽑게 된다면 isOk 함수를 통해 아이디들을 확인한다.

요기가 아이디들 확인 로직

if(!isOk(check[i], ban[i])) {
                    allOk = false;
                    break;
                }

요기가 무작위 로직

for(int i = 0 ; i < user.length ; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            check[depth] = user[i];
            backTracking(depth+1, user, ban);
            visited[i] = false;
        }

---

유의할 점
여기선,
제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.
라는 조건이 있다. 즉,
만약에 {"a", "b", "c"} {"c", "b", "a"} 와 같이 순서는 달라도 내용물은 전부 하나씩 매칭시켜 같은 배열을 세주라고 하면 하나의 배열로 세야 한다.

여기서 나는 디버깅이 필요했다.
처음에는 아래와 같이 사용해서 중복되는 친구들도 세줘서 틀린 답을 return했다.

if(allOk) answer++;   

그래서, 아래와 같이 고쳤다.
바로 HashSet<HashSet<String>> 을 이용하는것이다.

		  if(allOk) {
                HashSet<String> s = new HashSet<>();
                for(int i = 0 ; i < check.length ; i++) {
                    s.add(check[i]);
                }
                answer.add(new HashSet<>(s));
           }

---

약간 아쉽다. 처음부터 맞췄으면 훨씬 더 기분 좋았을텐데.