[프로그래머스] 불량 사용자

문제 설명

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

문제 풀이

• 간단한 DFS 문제였다.
• 배열의 길이가 최대 8밖에 되지 않기 때문에 ban id에 매칭되는 user id 맵을 만들어주고
  dfs를 진행하며 각 ban id에 매칭되는 user id를 매칭해주되 bit masking을 이용하여 방문처리를 해주었다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N, M, result = 0;
    public String[] UI, BI;
    public List<List<Integer>> map;
    public boolean chk[];
    
    public void dfs(int ind, int mask) {
        //결과 더해줌 
        if (ind == M) {
            if (!chk[mask]) {
                chk[mask] = true;
                result++;
            }
            return;
        }
        for (int i = 0; i < map.get(ind).size(); i++) {
            int next = map.get(ind).get(i);
            if ((mask & 2 << next) != 0) continue;
            dfs(ind+1, mask + (2 << next));
        }
    }

    public int solution(String[] user_id, String[] banned_id) {
        //초기화 
        N = user_id.length;
        M = banned_id.length;
        UI = user_id;
        BI = banned_id;
        chk = new boolean[2 << N];
        map = new ArrayList<>();
        for (int i = 0; i < M; i++)
            map.add(new ArrayList<>());
        //일치하는지 확인 후 map 만들어줌 
        for (int i = 0; i < M; i++) {
            String banId = BI[i];
            for (int j = 0; j < N; j++) {
                String userId = UI[j];
                if (banId.length() != userId.length()) continue;
                boolean flag = true;
                for (int k = 0; k < banId.length(); k++) {
                    if (banId.charAt(k) == '*')
                        continue;
                    else if (banId.charAt(k) != userId.charAt(k)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) map.get(i).add(j);
            }
        }
        //dfs 확인 
        dfs(0, 0);
        return result;
    }
}