[Programmers] 불량 사용자

처음 문제를 접했을 때 설계에 상당히 많은 시간을 사용하였다.

단순 문자열 파싱 문제인지 알았는데, 자세히 보니 전혀 다른 문제였다. 출력의 경우의 수를 자세히 보다 보니 특정한 규칙을 찾게 되었다. 이차원 배열이 있고, 가로축을 user_id, 세로축을 banned_id라고 하고 패턴이 매칭되면 1을 둔다고 가정한다면, 맨처음 입력 예시에선 다음과 같이 적용이 된다.

                "frodo" "fradi" "crodo" "abc123" "frodoc"
"fro*d*"          1        1        0          0            0     
"abc1**"          0        0        0          1            0     
이에 따른 출력은 2가지 경우로 frodo, abc123  과 fradi, abc123 가 나오게 된다.

여기서 찾은 규칙은 패턴이 매칭되는 1에 한해서 각행마다 하나의 열을 선택하게 되고, 다음행에선 선택이 안된 열에 대해 선택이 가능하다는 규칙을 찾게 되었다. 즉, N-Queen과 비슷한 원리의 백트래킹 문제로 생각하여 풀어보았다.
백트래킹을 사용하여 마지막 행까지 추적해보니 결과값을 얻을 수 있었다. 다만, 주의할점이 하나 있었는데 중복이 되는 해에대해선 1나로 카운팅을 해준다는 점이었다. 그래서 set을 이용하였고, set중에서도 가장 속도가 빠른 hashSet을 사용하여 최종 결과를 얻을 수 있었다.

package programmers;
 
import java.util.HashSet;
import java.util.Set;
 
public class Solution_2019카카오겨울_불량사용자 {
    public static void main(String[] args) {
        String[] user_id= {"frodo", "fradi", "crodo", "abc123", "frodoc"};
        
//        String[] banned_id= {"fr*d*", "abc1**"};
//        String[] banned_id= {"*rodo", "*rodo", "******"};
        String[] banned_id= {"fr*d*", "*rodo", "******", "******"};
    
        System.out.println(solution(user_id,banned_id));
    }
    
    static int[][] map;
    static boolean[] visit;
    
    static Set<String> set;
    static int R,C;
 
    static int solution(String[] user_id, String[] banned_id) {
        R=banned_id.length;
        C=user_id.length;
        
        map=new int[R][C];
        
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                String ban=banned_id[i];
                String user=user_id[j];
                
                if(user.length() == ban.length()) {    //길이가 같다면 확인
                    boolean flag=true;
                    for(int index=0;index<user.length()&&flag;index++) {
                        if(ban.charAt(index)!='*' && (ban.charAt(index)!=user.charAt(index)))
                            flag=false;
                    }
                    map[i][j]=flag?1:0;    //카운팅
                }
            }
        }
        
        visit=new boolean[C];
        
//        for(int i=0;i<C;i++) {
//            if(map[0][i]==1) {
//                visit[i]=true;
//                dfs(1);
//            }
//            
//        }
        set=new HashSet<>();
        dfs(0);
        
//        for(int i=0;i<R;i++) {
//            for(int j=0;j<C;j++) {
//                System.out.print(map[i][j]);
//            }
//            System.out.println();
//        }
        
        return set.size();
    }
    
    static void dfs(int depth) {
        if(depth==R) {
            String answer="";
            
            for(int i=0;i<C;i++) {
                if(visit[i]==true) {
                    answer+=i;
                }
            }
//            System.out.println(answer);
            set.add(answer);
            return;
        }
        
        for(int i=0;i<C;i++) {
            if(map[depth][i]==1 && visit[i]==false) {
                visit[i]=true;
                dfs(depth+1);
                visit[i]=false;
            }
        }
        
    }
    
}