[JAVA] 2019 카카오 개발자 겨울 인턴십 【불량 사용자】

---

백트래킹 방식으로, banned_id에 해당하는 갯수만큼의 조합을 모두 구한다.(getAllCases)

 

그 조합 순서가, banned_id에 있는 정규식 순서대로 매칭했을 때 일치하면(checkRegex) 정렬한다음 Set 자료구조에 넣는다.(addAns)

 

Set은 제네릭 타입을 String으로 하였는데, 조합을 문자열로 그대로 더한것으로 중복체크를 하였다.

 

아이디어를 떠올리는게 생각보다 금방 떠오르지 않았고, 처음에 문제를 풀었을때는 너무 가독성 없이 풀었어서 다시 풀었던 문제다.

 

---

import java.util.*;
import java.util.regex.*;
class Solution {
    Stack<String> s;
    HashSet<String> set;
    HashSet<String> ans;

    public int solution(String[] user_id, String[] banned_id) {
        s = new Stack<>();
        set = new HashSet<>();
        ans = new HashSet<>();

        getAllCases(user_id, banned_id);

        return ans.size();
    }

    void getAllCases(String[] user_id, String[] banned_id){
        if(s.size()==banned_id.length){
            String[] list = s.toArray(new String[s.size()]);
            if(checkRegex(list,banned_id)){
                addAns(list);
            }
            return;
        }

        for(int i=0;i<user_id.length;i++){
            String id = user_id[i];
            if(s.contains(id)){
                continue;
            }
            s.push(id);
            getAllCases(user_id,banned_id);
            s.pop();
        }
    }

    boolean checkRegex(String[] list, String[] banned_id){
        for(int i=0;i<banned_id.length;i++){
            String regex = banned_id[i].replaceAll("\\*",".");
            Pattern p = Pattern.compile(regex);
            Matcher m = p.matcher(list[i]);
            if(m.find()){
                if(m.group().length()!=list[i].length()){
                    return false;
                }
            }else{
                return false;
            }
        }
        return true;
    }

    void addAns(String[] list){
        Arrays.sort(list);
        StringBuilder sb = new StringBuilder();
        for(String str : list){
            sb.append(str);
        }
        ans.add(sb.toString());
    }

}