2019 카카오 개발자 겨울 인턴쉽 - 불량 사용자(순열, 해시, 정규표현식) - Java 풀이

https://programmers.co.kr/learn/courses/30/lessons/64064

코딩테스트 연습 - 불량 사용자

- user_id와 banned_id 원소가 1대1 매칭이 되어야 한다. 그래서 처음에는 banned_id 각각에 해당될 수 있는 경우의 수를 모두 세는 것으로 접근하였다가 중복처리를 하기가 힘들었다. 
- user_id 갯수가 8 이하이기 때문에 banned_id의 갯수만큼 순서대로 뽑으면서 중복을 허락하지 않는 순열을 만들어도 최대 8P4 밖에 안되기 때문에 user_id에서 banned_id 갯수만큼 뽑는 순열을 재귀적으로 만들고, 불량 사용자 배열의 정규표현식에 1대1 매치가 되는 순열은 해시에 넣어 중복처리를 하였다.

- boolean regex = Pattern.matches(pattern, val) 

import java.util.*;
import java.util.regex.*; //  boolean regex = Pattern.matches(pattern, val);

class Solution {
    List<String> pick = new ArrayList<>();
    boolean[] check = new boolean[8];
    
    Set<Set<String>> ans = new HashSet<>();
    
    public int solution(String[] user_id, String[] banned_id) { // 8P4 = 1천
        for(int i = 0; i < banned_id.length; ++i) {
            banned_id[i] = banned_id[i].replace("*", ".");
        }
        
        go(0, user_id, banned_id);
        return ans.size();
    }
    
    void go(int idx, String[] user_id, String[] banned_id) {
        if(idx == banned_id.length) {
            for(int i = 0; i < banned_id.length; ++i) {
                if(Pattern.matches(banned_id[i], pick.get(i)) == false) return;
            }
            
            ans.add(new HashSet<String>(pick));
            return;
        }
        
        for(int i = 0; i < user_id.length; ++i) {
            if(check[i]) continue;
            
            check[i] = true;
            pick.add(user_id[i]);
            go(idx + 1, user_id, banned_id);
            
            pick.remove(idx);
            check[i] = false;
        }
    }
}